String Problems

Problem 1: Longest Common Prefix

Explanation:

Given an array of strings, find the longest common prefix among them. If no common prefix exists, return an empty string.

Approach:

1. Horizontal Scanning:
   • Start with the first string as the prefix.
   • Compare it with each subsequent string, reducing the prefix as needed.
2. Terminate on Mismatch: If at any point the prefix becomes empty, return "".

Time & Space Complexity:

• Time Complexity: O(n * m), where n is the number of strings and m is the length of the longest string.
• Space Complexity: O(1), as we use no extra space.

Java Implementation:

public class LongestCommonPrefix {
    /**
     * Finds the longest common prefix among an array of strings.
     * @param strs - array of strings
     * @return longest common prefix
     */
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }
    
    public static void main(String[] args) {
        String[] strs = {"flower", "flow", "flight"};
        System.out.println("Output: " + longestCommonPrefix(strs));
    }
}

Example:

Input:

strs = ["flower", "flow", "flight"]

Output:

"fl"

Edge Cases Considered:

• No common prefix → Should return "".
• One string in the array → Should return the string itself.
• All strings are identical → Should return the full string.

---

Problem 2: Valid Anagram

Explanation:

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Approach:

1. Frequency Counting Approach:
   • Use an array of size 26 to count character frequencies in s and t.
   • If all counts match, return true.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the strings once.
• Space Complexity: O(1), using a fixed-size array.

Java Implementation:

public class ValidAnagram {
    /**
     * Checks if two strings are anagrams using frequency counting.
     * @param s - first input string
     * @param t - second input string
     * @return true if they are anagrams, false otherwise
     */
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int num : count) {
            if (num != 0) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        String s = "anagram", t = "nagaram";
        System.out.println("Output: " + isAnagram(s, t));
    }
}

Example:

Input:

s = "anagram", t = "nagaram"

Output:

true

Edge Cases Considered:

• Strings of different lengths → Should return false.
• Same characters but different counts → Should return false.
• Identical strings → Should return true.

---

Problem 3: Valid Parentheses

Explanation:

Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

Approach:

1. Use a Stack:
   • Push opening brackets onto a stack.
   • Pop from the stack when encountering a closing bracket and check if it matches.
   • If the stack is empty at the end, return true; otherwise, return false.

Time & Space Complexity:

• Time Complexity: O(n), as we traverse the string once.
• Space Complexity: O(n), for the stack in the worst case.

Java Implementation:

import java.util.Stack;

public class ValidParentheses {
    /**
     * Checks if the given string contains valid parentheses.
     * @param s - input string containing brackets
     * @return true if valid, false otherwise
     */
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        String s = "()[]{}";
        System.out.println("Output: " + isValid(s));
    }
}

Example:

Input:

s = "()[]{}"

Output:

true

Edge Cases Considered:

• Empty string → Should return true.
• Single closing bracket → Should return false.
• Unmatched opening brackets → Should return false.

---

Problem 4: Reverse Vowels of a String

Explanation:

Given a string s, reverse only the vowels in the string and return the modified string.

Approach:

1. Two-Pointer Technique:
   • Use two pointers, one starting from the beginning and the other from the end.
   • Swap vowels while moving the pointers toward each other.
2. Continue Until Pointers Meet: Stop when both pointers cross.

Time & Space Complexity:

• Time Complexity: O(n), since we traverse the string once.
• Space Complexity: O(n) if we use a mutable string representation, or O(1) if modifying in place.

Java Implementation:

import java.util.*;

public class ReverseVowels {
    /**
     * Reverses only the vowels in the given string.
     * @param s - input string
     * @return string with vowels reversed
     */
    public static String reverseVowels(String s) {
        char[] arr = s.toCharArray();
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        int left = 0, right = arr.length - 1;
        
        while (left < right) {
            while (left < right && !vowels.contains(arr[left])) left++;
            while (left < right && !vowels.contains(arr[right])) right--;
            char temp = arr[left];
            arr[left++] = arr[right];
            arr[right--] = temp;
        }
        return new String(arr);
    }
    
    public static void main(String[] args) {
        String s = "hello";
        System.out.println("Output: " + reverseVowels(s));
    }
}

Example:

Input:

s = "hello"

Output:

"holle"

Edge Cases Considered:

• No vowels in the string → Should return the original string.
• All vowels → Should reverse the entire string.
• String with mixed cases → Should correctly swap uppercase and lowercase vowels.

---

Problem 5: Remove All Adjacent Duplicates in String

Explanation:

Given a string s, remove adjacent duplicate characters repeatedly until no adjacent duplicates remain.

Approach:

1. Use a Stack:
   • Iterate through the string and push characters onto the stack.
   • If the top of the stack matches the current character, pop it.
2. Construct Result from Stack: The final stack content forms the resulting string.

Time & Space Complexity:

• Time Complexity: O(n), as we traverse the string once.
• Space Complexity: O(n), for storing the stack content.

Java Implementation:

import java.util.*;

public class RemoveAdjacentDuplicates {
    /**
     * Removes all adjacent duplicates in a string.
     * @param s - input string
     * @return string with adjacent duplicates removed
     */
    public static String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }
        return result.toString();
    }
    
    public static void main(String[] args) {
        String s = "abbaca";
        System.out.println("Output: " + removeDuplicates(s));
    }
}

Example:

Input:

s = "abbaca"

Output:

"ca"

Edge Cases Considered:

• All characters are duplicates → Should return an empty string.
• No duplicates → Should return the original string.
• String with mixed characters → Should correctly process adjacent duplicates only.

---

Problem 6: Find the Index of the First Occurrence in a String

Explanation:

Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Approach:

1. Brute Force Approach:
   • Iterate through haystack and compare each substring with needle.
2. KMP Algorithm (Optimized Approach):
   • Preprocess needle to create the longest prefix-suffix array.
   • Use the array to skip unnecessary comparisons in haystack.

Time & Space Complexity:

• Brute Force: O(n * m), where n is the length of haystack and m is the length of needle.
• KMP Algorithm: O(n + m), since it preprocesses needle in O(m) and searches in O(n).

Java Implementation:

public class FirstOccurrence {
    /**
     * Finds the index of the first occurrence of needle in haystack.
     * @param haystack - input string
     * @param needle - substring to search for
     * @return index of first occurrence, or -1 if not found
     */
    public static int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
    
    public static void main(String[] args) {
        String haystack = "hello", needle = "ll";
        System.out.println("Output: " + strStr(haystack, needle));
    }
}

Example:

Input:

haystack = "hello", needle = "ll"

Output:

2

Edge Cases Considered:

• Empty needle → Should return 0.
• needle longer than haystack → Should return -1.
• Multiple occurrences → Should return the first occurrence.

---

Problem 7: Letter Combinations of a Phone Number

Explanation:

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent.

Approach:

1. Backtracking:
   • Use a mapping of digits to letters.
   • Recursively generate all possible combinations.

Time & Space Complexity:

• Time Complexity: O(4^n), where n is the length of digits.
• Space Complexity: O(4^n), for storing output combinations.

Java Implementation:

import java.util.*;

public class LetterCombinations {
    private static final String[] KEYPAD = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    /**
     * Generates all possible letter combinations from a phone number.
     * @param digits - input digit string
     * @return list of letter combinations
     */
    public static List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits.isEmpty()) return result;
        backtrack(result, digits, new StringBuilder(), 0);
        return result;
    }
    
    private static void backtrack(List<String> result, String digits, StringBuilder current, int index) {
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }
        String letters = KEYPAD[digits.charAt(index) - '0'];
        for (char c : letters.toCharArray()) {
            current.append(c);
            backtrack(result, digits, current, index + 1);
            current.deleteCharAt(current.length() - 1);
        }
    }
    
    public static void main(String[] args) {
        String digits = "23";
        System.out.println("Output: " + letterCombinations(digits));
    }
}

Example:

Input:

digits = "23"

Output:

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Edge Cases Considered:

• Empty input → Should return an empty list.
• Single digit → Should return all letters mapped to that digit.
• Digits containing 7 or 9 (four letters) → Should correctly generate combinations.

---

Problem 8: Generate Parentheses

Explanation:

Given n pairs of parentheses, generate all valid combinations of well-formed parentheses.

Approach:

1. Backtracking:
   • Use recursive function to generate valid parentheses.
   • Ensure valid placement by tracking open and close counts.

Time & Space Complexity:

• Time Complexity: O(4^n / sqrt(n)), based on the Catalan number.
• Space Complexity: O(4^n / sqrt(n)), since we store all valid combinations.

Java Implementation:

import java.util.*;

public class GenerateParentheses {
    /**
     * Generates all valid combinations of n pairs of parentheses.
     * @param n - number of pairs
     * @return list of valid parentheses strings
     */
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }
    
    private static void backtrack(List<String> result, String current, int open, int close, int max) {
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }
        if (open < max) backtrack(result, current + "(", open + 1, close, max);
        if (close < open) backtrack(result, current + ")", open, close + 1, max);
    }
    
    public static void main(String[] args) {
        int n = 3;
        System.out.println("Output: " + generateParenthesis(n));
    }
}

Example:

Input:

n = 3

Output:

["((()))", "(()())", "(())()", "()(())", "()()()"]

Edge Cases Considered:

• n = 0 → Should return an empty list.
• n = 1 → Should return ("()").
• Large n → Should efficiently generate all valid combinations.

---

Problem 9: Longest Substring Without Repeating Characters

Explanation:

Given a string s, find the length of the longest substring without repeating characters.

Approach:

1. Sliding Window Technique:
   • Use two pointers (left and right) to maintain a window of unique characters.
   • Use a HashSet to track characters in the window.
   • Expand the window by moving right until a duplicate is found.
   • Shrink the window by moving left until duplicates are removed.

Time & Space Complexity:

• Time Complexity: O(n), as each character is processed at most twice.
• Space Complexity: O(min(m, n)), where m is the character set size (e.g., 26 for lowercase English letters).

Java Implementation:

import java.util.HashSet;

public class LongestSubstringWithoutRepeating {
    /**
     * Finds the length of the longest substring without repeating characters.
     * @param s - input string
     * @return length of the longest substring
     */
    public static int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int left = 0, maxLength = 0;
        for (int right = 0; right < s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left++));
            }
            set.add(s.charAt(right));
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
    
    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("Output: " + lengthOfLongestSubstring(s));
    }
}

Example:

Input:

s = "abcabcbb"

Output:

3

Edge Cases Considered:

• Empty string → Should return 0.
• All unique characters → Should return the string length.
• All same characters → Should return 1.

---

Problem 10: Palindrome Partitioning II

Explanation:

Given a string s, partition s into the minimum number of cuts such that every substring is a palindrome.

Approach:

1. Dynamic Programming:
   • Use dp[i] to store the minimum cuts needed for substring s[0...i].
   • Use a helper function to check if s[i...j] is a palindrome.
   • Update dp[i] using previous values to minimize cuts.

Time & Space Complexity:

• Time Complexity: O(n^2), since we precompute palindromes and update the dp array.
• Space Complexity: O(n^2), due to the palindrome table.

Java Implementation:

public class PalindromePartitioningII {
    /**
     * Finds the minimum cuts needed to partition a string into palindromes.
     * @param s - input string
     * @return minimum cuts needed
     */
    public static int minCut(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        int[] dp = new int[n];
        
        for (int i = 0; i < n; i++) {
            int minCuts = i;
            for (int j = 0; j <= i; j++) {
                if (s.charAt(j) == s.charAt(i) && (i - j <= 1 || isPalindrome[j + 1][i - 1])) {
                    isPalindrome[j][i] = true;
                    minCuts = (j == 0) ? 0 : Math.min(minCuts, dp[j - 1] + 1);
                }
            }
            dp[i] = minCuts;
        }
        return dp[n - 1];
    }
    
    public static void main(String[] args) {
        String s = "aab";
        System.out.println("Output: " + minCut(s));
    }
}

Example:

Input:

s = "aab"

Output:

1

Edge Cases Considered:

• Already a palindrome → Should return 0.
• All distinct characters → Should return n - 1.
• Multiple palindrome partitions possible → Should return the minimum cuts.

---

Problem 11: Longest Palindromic Substring

Explanation:

Given a string s, find the longest palindromic substring.

Approach:

1. Manacher’s Algorithm (Optimized Space):
   • Transform the string to handle even-length palindromes.
   • Use a palindrome expansion technique with a center and right boundary.
   • Reduce space complexity from O(n) to O(1).

Time & Space Complexity:

• Time Complexity: O(n), since we iterate through the string once.
• Space Complexity: O(1), as we compute in place.

Java Implementation:

public class LongestPalindromicSubstring {
    /**
     * Finds the longest palindromic substring.
     * @param s - input string
     * @return longest palindromic substring
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    
    private static int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
    
    public static void main(String[] args) {
        String s = "babad";
        System.out.println("Output: " + longestPalindrome(s));
    }
}

Example:

Input:

s = "babad"

Output:

"bab" or "aba"

Edge Cases Considered:

• Single character string → Should return the character itself.
• All characters unique → Any single character is a valid palindrome.
• Even-length palindrome → Should correctly handle.

---

Problem 12: Isomorphic Strings

Explanation:

Given two strings s and t, determine if they are isomorphic.

Approach:

1. Two Hash Maps:
   • Map characters of s to t and vice versa.
   • Ensure the mapping is consistent.

Time & Space Complexity:

• Time Complexity: O(n), since we iterate once.
• Space Complexity: O(1), since character sets are fixed.

Java Implementation:

import java.util.HashMap;

public class IsomorphicStrings {
    /**
     * Determines if two strings are isomorphic.
     * @param s - first string
     * @param t - second string
     * @return true if isomorphic, false otherwise
     */
    public static boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        HashMap<Character, Character> map1 = new HashMap<>();
        HashMap<Character, Character> map2 = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i), c2 = t.charAt(i);
            if (map1.containsKey(c1) && map1.get(c1) != c2 || map2.containsKey(c2) && map2.get(c2) != c1) {
                return false;
            }
            map1.put(c1, c2);
            map2.put(c2, c1);
        }
        return true;
    }
    
    public static void main(String[] args) {
        String s = "egg", t = "add";
        System.out.println("Output: " + isIsomorphic(s, t));
    }
}

Example:

Input:

s = "egg", t = "add"

Output:

true

Edge Cases Considered:

• Different lengths → Should return false.
• Same characters but inconsistent mapping → Should return false.
• Already matching one-to-one → Should return true.

---

Problem 13: Integer to English Words

Explanation:

Convert a non-negative integer num to English words.

Approach:

1. Divide and Conquer:
   • Recursively convert groups of three digits (thousands, millions, billions).
   • Use a lookup table for numbers.

Time & Space Complexity:

• Time Complexity: O(1), since there are limited number mappings.
• Space Complexity: O(1), as the output string is constant.

Java Implementation:

public class IntegerToEnglishWords {
    private static final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private static final String[] TENS = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    private static final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};
    
    public static String numberToWords(int num) {
        if (num == 0) return "Zero";
        String words = "";
        int i = 0;
        while (num > 0) {
            if (num % 1000 != 0) words = helper(num % 1000) + THOUSANDS[i] + " " + words;
            num /= 1000;
            i++;
        }
        return words.trim();
    }
    
    private static String helper(int num) {
        if (num == 0) return "";
        else if (num < 20) return LESS_THAN_20[num] + " ";
        else if (num < 100) return TENS[num / 10] + " " + helper(num % 10);
        else return LESS_THAN_20[num / 100] + " Hundred " + helper(num % 100);
    }
    
    public static void main(String[] args) {
        int num = 1234567;
        System.out.println("Output: " + numberToWords(num));
    }
}

Example:

Input:

num = 1234567

Output:

"One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Edge Cases Considered:

• Zero input → Should return "Zero".
• Exact multiples of thousand → Should correctly format.
• Very large numbers → Should handle up to billions.

---

Problem 14: Integer to Roman

Explanation:

Convert an integer to its Roman numeral representation.

Approach:

1. Greedy Approach with Lookup Table:
   • Define integer values for Roman symbols.
   • Iteratively subtract the largest possible value and append the corresponding Roman symbol.

Time & Space Complexity:

• Time Complexity: O(1), since there are only a fixed number of Roman numerals.
• Space Complexity: O(1), as we store a constant mapping.

Java Implementation:

public class IntegerToRoman {
    private static final int[] VALUES = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    private static final String[] SYMBOLS = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    
    public static String intToRoman(int num) {
        StringBuilder roman = new StringBuilder();
        for (int i = 0; i < VALUES.length; i++) {
            while (num >= VALUES[i]) {
                num -= VALUES[i];
                roman.append(SYMBOLS[i]);
            }
        }
        return roman.toString();
    }
    
    public static void main(String[] args) {
        int num = 1994;
        System.out.println("Output: " + intToRoman(num));
    }
}

Example:

Input:

num = 1994

Output:

"MCMXCIV"

Edge Cases Considered:

• Smallest possible number (1) → Should return “I”.
• Largest possible number (3999) → Should return “MMMCMXCIX”.

---

Problem 15: Reverse Integer

Explanation:

Given an integer x, return its reversed integer. If reversing causes an overflow, return 0.

Approach:

1. Math Operations:
   • Use modulo to extract digits and build the reversed number.
   • Check for overflow before multiplying and adding.

Time & Space Complexity:

• Time Complexity: O(log n), since the number of digits is logarithmic.
• Space Complexity: O(1), as we use a constant amount of space.

Java Implementation:

public class ReverseInteger {
    public static int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
    
    public static void main(String[] args) {
        int x = 123;
        System.out.println("Output: " + reverse(x));
    }
}

Example:

Input:

x = 123

Output:

321

Edge Cases Considered:

• Negative numbers → Should return a negative reversed number.
• Numbers ending in zero → Should correctly remove leading zeros.
• Overflow cases → Should return 0.

---

Problem 16: Excel Sheet Column Title

Explanation:

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

Approach:

1. Base-26 Conversion:
   • Convert columnNumber to base-26 where A = 1, B = 2, ..., Z = 26.
   • Decrement columnNumber by 1 before modulo to align indexing.

Time & Space Complexity:

• Time Complexity: O(log n), since conversion takes log base-26 steps.
• Space Complexity: O(log n), for storing the output string.

Java Implementation:

public class ExcelSheetColumnTitle {
    public static String convertToTitle(int columnNumber) {
        StringBuilder title = new StringBuilder();
        while (columnNumber > 0) {
            columnNumber--;
            title.append((char) ('A' + columnNumber % 26));
            columnNumber /= 26;
        }
        return title.reverse().toString();
    }
    
    public static void main(String[] args) {
        int columnNumber = 28;
        System.out.println("Output: " + convertToTitle(columnNumber));
    }
}

Example:

Input:

columnNumber = 28

Output:

"AB"

Edge Cases Considered:

• Smallest value (1) → Should return “A”.
• Exact multiples of 26 → Should correctly convert (e.g., 26 → “Z”, 27 → “AA”).
• Large numbers → Should still compute correctly.

---

Problem 17: Valid Tic-Tac-Toe State

Explanation:

Given a Tic-Tac-Toe board represented as an array of strings, determine if the board state is valid.

Approach:

1. Rules-based Validation:
   • Count the number of Xs and Os.
   • Ensure turn ordering is valid (X must be equal to or one more than O).
   • Check if both players have won simultaneously (invalid case).
   • Ensure winning conditions match the turn sequence.

Time & Space Complexity:

• Time Complexity: O(1), since the board is always 3×3.
• Space Complexity: O(1), as we use a fixed amount of storage.

Java Implementation:

public class ValidTicTacToe {
    public static boolean validTicTacToe(String[] board) {
        int xCount = 0, oCount = 0;
        for (String row : board) {
            for (char c : row.toCharArray()) {
                if (c == 'X') xCount++;
                else if (c == 'O') oCount++;
            }
        }
        if (oCount > xCount || xCount - oCount > 1) return false;
        boolean xWins = isWinner(board, 'X');
        boolean oWins = isWinner(board, 'O');
        if (xWins && oWins) return false;
        if (xWins && xCount == oCount) return false;
        if (oWins && xCount > oCount) return false;
        return true;
    }
    
    private static boolean isWinner(String[] board, char player) {
        for (int i = 0; i < 3; i++) {
            if (board[i].charAt(0) == player && board[i].charAt(1) == player && board[i].charAt(2) == player) return true;
            if (board[0].charAt(i) == player && board[1].charAt(i) == player && board[2].charAt(i) == player) return true;
        }
        return (board[0].charAt(0) == player && board[1].charAt(1) == player && board[2].charAt(2) == player) ||
               (board[0].charAt(2) == player && board[1].charAt(1) == player && board[2].charAt(0) == player);
    }
    
    public static void main(String[] args) {
        String[] board = {"XOX", "O O", "XOX"};
        System.out.println("Output: " + validTicTacToe(board));
    }
}

Example:

Input:

board = ["XOX", "O O", "XOX"]

Output:

false

Edge Cases Considered:

• Too many or too few X/O counts → Should return false.
• Both players winning simultaneously → Should return false.
• Valid board sequence → Should return true.

---

Problem 18: Group Anagrams

Explanation:

Given an array of strings, group anagrams together.

Approach:

1. Prime Factorization Hashing (Optimized Approach):
   • Assign each character a unique prime number.
   • Compute a product of primes as a hash key for each string.
   • Use a HashMap to group anagrams by their unique prime product.

Time & Space Complexity:

• Time Complexity: O(n * k), where n is the number of words and k is the average word length.
• Space Complexity: O(n * k), since we store grouped results.

Java Implementation:

import java.util.*;

public class GroupAnagrams {
    private static final int[] PRIMES = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
    
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<Long, List<String>> map = new HashMap<>();
        for (String s : strs) {
            long hash = computeHash(s);
            map.putIfAbsent(hash, new ArrayList<>());
            map.get(hash).add(s);
        }
        return new ArrayList<>(map.values());
    }
    
    private static long computeHash(String s) {
        long hash = 1;
        for (char c : s.toCharArray()) {
            hash *= PRIMES[c - 'a'];
        }
        return hash;
    }
    
    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println("Output: " + groupAnagrams(strs));
    }
}

Example:

Input:

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

Output:

[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Edge Cases Considered:

• All unique words → Should return each word as its own group.
• All words are anagrams → Should return a single group.
• Mixed case scenarios → Should correctly group them.

---