Strings: Classic Algorithms and Memory Semantics

Fundamental String Operations

// Common Java String APIs
s.length()               // Length
s.charAt(i)              // Character at index i
s.substring(l, r)        // Substring [l, r)
s.indexOf("ab")          // Find substring
s.contains("ab")         // Check inclusion
s.replace("a", "b")      // Replace
s.split(" ")             // Split by delimiter
s.toCharArray()          // Convert to char array
s.toLowerCase() / s.toUpperCase()
String.valueOf(arr)      // Convert char array to string
new StringBuilder(s).reverse().toString()  // Reverse string

Two Pointers and Reversal

Reversing a String

void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char tmp = s[left]; 
        s[left] = s[right]; 
        s[right] = tmp;
        left++; 
        right--;
    }
}

Reverse Words in a String (LeetCode 151)

Clean up leading/trailing/multiple spaces and reverse the order of words:

String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");  // Split by one or more spaces
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        sb.append(words[i]);
        if (i > 0) sb.append(' ');
    }
    return sb.toString();
}

Palindrome Problems

Valid Palindrome (LeetCode 125)

boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        // Skip non-alphanumeric characters
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
        
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
            return false;
        left++; 
        right--;
    }
    return true;
}

Longest Palindromic Substring (LeetCode 5)

Center Expansion Method: Treat each character (or pair of characters) as the center and expand outwards:

String longestPalindrome(String s) {
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
        int odd = expand(s, i, i);         // Odd length palindrome
        int even = expand(s, i, i + 1);    // Even length palindrome
        int len = Math.max(odd, even);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);
}

int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { 
        l--; 
        r++; 
    }
    return r - l - 1;
}

Palindromic Substrings (LeetCode 647)

Similar center expansion, counting the total number of valid expansions:

int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += countExpand(s, i, i);       // Odd palindromes
        count += countExpand(s, i, i + 1);   // Even palindromes
    }
    return count;
}

int countExpand(String s, int l, int r) {
    int count = 0;
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        count++; 
        l--; 
        r++;
    }
    return count;
}

String Matching (KMP Algorithm)

KMP avoids the redundant scanning of the brute force O(n·m) approach by pre-computing a "Partial Match Table" (the next array) to achieve O(n+m).

int[] buildNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];  // next[i] = longest proper prefix that is also a suffix of pattern[0..i]
    int k = 0;                 // length of current longest prefix-suffix
    for (int i = 1; i < m; i++) {
        while (k > 0 && pattern.charAt(i) != pattern.charAt(k)) k = next[k - 1];
        if (pattern.charAt(i) == pattern.charAt(k)) k++;
        next[i] = k;
    }
    return next;
}

int kmpSearch(String text, String pattern) {
    if (pattern.isEmpty()) return 0;
    int[] next = buildNext(pattern);
    int n = text.length(), m = pattern.length();
    int k = 0;  // Number of characters currently matched
    for (int i = 0; i < n; i++) {
        while (k > 0 && text.charAt(i) != pattern.charAt(k)) k = next[k - 1];
        if (text.charAt(i) == pattern.charAt(k)) k++;
        if (k == m) return i - m + 1;  // Success, return start index
    }
    return -1;
}

Production Reality: In production Java, you often use s.indexOf(p) (which uses implementations similar to BM or Boyer-Moore-Horspool). However, understanding KMP's philosophy (leveraging past match information to avoid back-tracking) is crucial for advanced algorithmic logic.

String Transformation and Grouping

Group Anagrams (LeetCode 49)

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] key = s.toCharArray();
        Arrays.sort(key);                         // Sorted string acts as the unique key
        map.computeIfAbsent(new String(key), k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

Valid Parentheses (LeetCode 20)

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    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();
}

Longest Common Prefix (LeetCode 14)

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].startsWith(prefix)) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

String Problem Quick Reference