Strings — 11 Problems, Every Trick

A string is just an array whose elements are characters — so every array technique carries over. This one sentence is the spine of both sessions: two pointers, in-place index rewriting, sliding window, and frequency counting all apply directly.

Substring vs. subsequence. A substring is contiguous ("cr" in "cric"). A subsequence is any set of characters kept in increasing index order, not necessarily contiguous ("cic", "rc"). A single character counts as a subsequence.

Reverse the order of words; a word is a run of non-space chars. Output has no leading/trailing spaces and exactly one space between words. " hello world " → "world hello".

Pattern: manual two-index string parse + prepend. Family: string tokenizing / index manipulation.

Practice: LeetCode 151↗ — Reverse Words in a String.

Brute force / library. split on whitespace, reverse the array, join with a space. Fine, but the manual version (no split) is worth doing to drill index manipulation, since a string is just a char array.

The approach. Walk with index i: skip any run of spaces, then use a second index j to capture the word [i..j) up to the next space. Instead of collecting words and reversing at the end, prepend each new word: result = word + " " + result. Reversal order comes for free.

public String reverseWords(String s) {
    String result = new String();
    int i = 0, n = s.length();
    while (i < n) {
        while (i < n && s.charAt(i) == ' ') i++;   // skip leading/extra spaces
        if (i >= n) break;                          // trailing spaces -> done
        int j = i + 1;
        while (j < n && s.charAt(j) != ' ') j++;    // capture word [i .. j-1]
        String sub = s.substring(i, j);
        if (result.length() == 0) result = sub;     // first word
        else result = sub + " " + result;           // PREPEND -> reversed order
        i = j + 1;
    }
    return result;
}

Edge cases. All spaces → empty string. Single word → returned unchanged. Multiple internal spaces → collapsed to one.

Why this matters. Manual tokenizing with two indices (skip-delimiter, then capture-token) is the reusable core for parsing CSV-like input, sentences, and version strings without library splits.

String of n/2 [ and n/2 ]; you may swap any two indices any number of times. Return the minimum swaps to make it balanced. "]["-style input → often 1.

Pattern: stack cancellation (or running balance). Family: bracket matching.

Practice: LeetCode 1963↗ — Minimum Number of Swaps to Make the String Balanced.

The approach. Sweep left to right. Push every [. On a ], if the stack top is a matching [, pop — that pair is already balanced and irrelevant. After the sweep, whatever ['s remain (count k) represent the unmatched openers; each swap fixes two of them, so the answer is ceil(k/2).

public int minSwaps(String s) {
    Stack<Character> st = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '[') {
            st.push('[');
        }
        // matched pair -> cancel it (guard: stack not empty)
        if (s.charAt(i) == ']' && st.size() != 0 && st.peek() == '[') {
            st.pop();
        }
    }
    int k = st.size();                 // unmatched '[' count
    return (k % 2 == 0) ? k / 2 : (k + 1) / 2;
}

Edge cases & bugs. Already balanced → empty stack → 0 swaps. [!] The empty-stack guard (st.size() != 0) matters: a leading ] must not pop an empty stack. This is exactly the edge case to watch.

Why this matters. "Cancel matched pairs, measure the leftover" is the template for valid-parentheses, min-add-to-make-valid, and remove-invalid-parentheses.

Return the number of palindromic substrings (contiguous) in s. "abc" → 3 (each single char).

Pattern: expand-around-center. Family: palindrome problems (siblings: Longest Palindromic Substring).

Practice: LeetCode 647↗ — Palindromic Substrings.

Brute force. Enumerate all O(n²) substrings, check each in O(n) → O(n³). The counting fact from the fundamentals section (n(n+1)/2 substrings) is exactly why the naive path is O(n³) and why you look for better.

The leap. Treat every index as the center of a palindrome and expand two pointers outward while the characters match, counting each successful expansion. Because palindromes are symmetric, you never need to re-examine a substring you already grew past. Run it twice per index: odd-length center (i, i) and even-length center (i, i+1). Total O(n²).

Recommended (counting, O(1) space) [+]:

public int countSubstrings(String s) {
    int n = s.length(), count = 0;
    for (int i = 0; i < n; i++) {
        count += expand(s, i, i);       // odd-length palindromes
        count += expand(s, i, i + 1);   // even-length palindromes
    }
    return count;
}
private int expand(String s, int l, int h) {
    int c = 0;
    while (l >= 0 && h < s.length() && s.charAt(l) == s.charAt(h)) {
        c++;      // s[l..h] is a palindrome
        l--; h++;
    }
    return c;
}

Edge cases. Empty string → 0. All-same ("aaa") → 6. Every single char always counts.

Interview follow-up. Same center-expansion, but track the widest span instead of a count → Longest Palindromic Substring. [+]

Why this matters. Expand-around-center is the go-to for any "palindrome inside a string" question and sidesteps the O(n³) trap.

Minimum insert / delete / replace operations to convert word1 into word2. "zwcmqpow" → "zwtcmqpow" → 1 (insert 't').

Pattern: two-string DP. Family: sequence-alignment DP (sibling of LCS).

Practice: LeetCode 72↗ — Edit Distance.

Brute force → recursion. Compare from the ends. If last chars match, no operation — recurse on (n-1, m-1). If they differ, you must do one of three operations and pay 1, then take the cheapest branch. Plain recursion recomputes the same (n, m) subproblems exponentially.

The three operations and how each moves the indices (the part the session drilled hardest):

• Replace word1's char to match word2 → both consumed → recurse (n-1, m-1).
• Delete word1's extra char → word1 shrinks, word2 unchanged → recurse (n-1, m).
• Insert into word1 to match word2's char → word2 shrinks, word1 unchanged → recurse (n, m-1).

Cost on a mismatch: 1 + min(insert, delete, replace).

public int minDis(String s1, String s2, int n, int m, int[][] dp) {
    if (n == 0) return m;              // build remaining m chars
    if (m == 0) return n;              // remove remaining n chars
    if (dp[n][m] != -1) return dp[n][m];   // memo hit

    if (s1.charAt(n - 1) == s2.charAt(m - 1)) {   // match -> no op
        return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp);
    }
    int insert  = minDis(s1, s2, n,     m - 1, dp);   // word2 shrinks
    int del     = minDis(s1, s2, n - 1, m,     dp);   // word1 shrinks
    int replace = minDis(s1, s2, n - 1, m - 1, dp);   // both shrink
    return dp[n][m] = 1 + Math.min(insert, Math.min(del, replace));
}
// driver: dp = new int[n+1][m+1] filled with -1; call minDis(w1, w2, n, m, dp)

Edge cases. Either string empty → length of the other. Identical strings → 0.

Interview follow-ups. Bottom-up int[n+1][m+1] table; space-optimize to two rows. [+] The recurrence without the replace branch (and counting deletions/insertions) reduces to LCS-based distance.

Why this matters. This is the canonical two-string DP: state = the two prefix lengths, branch on match vs. the three edits, memoize. Recognizing "two changing indices ⇒ 2D DP" transfers everywhere.

Evaluate a math expression string and return its integer value, honoring operator precedence. " 3+5 / 2 " → 5 (integer division: 5/2=2, 3+2=5).

Pattern: two stacks (operands + operators) with precedence rule. Family: expression parsing / stack evaluation.

Practice: LeetCode 227↗ — Basic Calculator II (handles + − × / without parentheses).

The approach. Keep two stacks: one for operands (numbers), one for operators. Scan the string. On a number, parse the full multi-digit value and push it. On an operator, before pushing it, repeatedly pop and apply any operator on top that has higher-or-equal precedence — because a lower-precedence operator must never sit above a higher one. After the scan, drain the operator stack. The last operand left is the answer.

public static int calculate(String s) {
    Stack<Integer> operands = new Stack<>();
    Stack<Character> operators = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            int num = 0;
            while (i < s.length() && Character.isDigit(s.charAt(i))) {
                num = num * 10 + (s.charAt(i) - '0');   // build multi-digit
                i++;
            }
            i--;                       // undo the extra ++ from the inner loop
            operands.push(num);
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            // apply higher-precedence ops sitting on top before pushing c
            while (!operators.isEmpty() && hasHigherPrecedence(operators.peek(), c)) {
                char op = operators.pop();
                int right = operands.pop(), left = operands.pop();
                operands.push(performOperation(left, right, op));
            }
            operators.push(c);
        }
    }
    while (!operators.isEmpty()) {     // drain remaining operators
        char op = operators.pop();
        int right = operands.pop(), left = operands.pop();
        operands.push(performOperation(left, right, op));
    }
    return operands.pop();
}
private static boolean hasHigherPrecedence(char op1, char op2) {
    // op1 (on stack) outranks op2 (incoming) when op1 is * or / and op2 is + or -
    return (op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-');
}
private static int performOperation(int left, int right, char op) {
    switch (op) {
        case '+': return left + right;
        case '-': return left - right;
        case '*': return left * right;
        case '/':
        if (right == 0) throw new ArithmeticException("Division by zero");
        return left / right;
    }
    return 0;
}

Edge cases & bugs. Leading/trailing/internal spaces are skipped naturally (non-digit, non-operator). Division by zero throws. Same-precedence operators evaluate left-to-right because the incoming equal-precedence op triggers the pop.

Note [!]. The precedence check as written only pops when the stack op is ×// and the incoming is +/−; for correct left-to-right handling of same-precedence chains (e.g. 6/2*3), also pop when precedence is equal. Verify against the platform's test cases.

Why this matters. The two-stack shunting approach generalizes to full calculators (with parentheses), reverse-Polish evaluation, and any precedence-driven parsing.

Keep each letter once so the result is the lexicographically smallest of all such strings, preserving relative order. Input "cbacdcbc" → "acdb".

Pattern: monotonic stack + greedy. Family: "smallest/largest subsequence via stack" (same shape as Remove K Digits, Smallest Subsequence).

Practice: LeetCode 316↗ — Remove Duplicate Letters (identical: LeetCode 1081↗ — Smallest Subsequence of Distinct Characters).

Brute force. Enumerate subsequences that contain each distinct char exactly once, keep the lexicographically smallest — exponential, useless. The realization: you can build the answer greedily left to right.

The leap. Walk the string keeping a stack of the answer so far. When the current char curr is smaller than the stack top and that top appears again later, pop the top — you'll re-add it later in a better position. This is exactly the precedence idea from the expression-evaluation problem: a lower-priority (smaller) char can't sit on top of a higher one that still has a future occurrence.

public String removeDuplicateLetters(String s) {
    int[] inStack = new int[26];            // 1 = char currently on stack
    HashMap<Character,Integer> last = new HashMap<>();
    Stack<Character> stack = new Stack<>();

    // last occurrence index of every char
    for (int i = 0; i < s.length(); i++) last.put(s.charAt(i), i);

    for (int i = 0; i < s.length(); i++) {
        char curr = s.charAt(i);
        if (inStack[curr - 'a'] == 1) continue;   // already placed -> skip

        // pop bigger tops that still appear later (so we can re-add them)
        while (!stack.isEmpty() && curr < stack.peek() && i < last.get(stack.peek())) {
            inStack[stack.pop() - 'a'] = 0;
        }
        stack.push(curr);
        inStack[curr - 'a'] = 1;
    }

    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) sb.append(stack.pop());
    return sb.reverse().toString();   // stack is top-first, so reverse
}

Edge cases & bugs. Empty string → empty result. All-unique input → string unchanged. [!] One version's final line is return sb.reverse(); that returns a StringBuilder, not a String — add .toString(). Uppercase input isn't handled by the size-26 array; you'd assume lowercase and clarify with the interviewer.

Why this matters. The stack-as-greedy-builder + "pop when a better future exists" pattern transfers directly to Remove K Digits, Create Maximum Number, and any "smallest/largest subsequence keeping order" problem.

Compress runs of equal chars into char + run-length, in place, and return the new length. ["a","a","b","b","c","c","c"] → first 6 slots become ["a","2","b","2","c","3"], return 6.

Pattern: in-place two-index rewrite. Family: array index-manipulation (like Remove Element, Remove Duplicates from Sorted Array).

Practice: LeetCode 443↗ — String Compression.

Brute force. Count frequencies into a HashMap, then rebuild — correct but O(n) extra space. In an interview the map answer is the expected "first" answer; the follow-up is always "reduce the space."

The leap. A string is just a character array, so use two indices in the same array: a read pointer i that scans a run and counts it, and a write pointer ans that overwrites position by position with the char followed by its count's digits. No auxiliary structure → O(1) space.

public int compress(char[] chars) {
    int ans = 0, i = 0;              // ans = write ptr, i = read ptr
    while (i < chars.length) {
        char curr = chars[i];
        int count = 0;
        while (i < chars.length && chars[i] == curr) { // count the run
            i++;
            count++;
        }
        chars[ans++] = curr;                 // write the char
        if (count != 1) {                    // write digits only if > 1
            for (char c : Integer.toString(count).toCharArray()) chars[ans++] = c;
        }
    }
    return ans;                              // new length
}

Edge cases & bugs. Single char → length 1, no count. All-same input of length k → char + digits of k. The write pointer never overtakes the read pointer because compressed output is never longer than the run it replaces.

Why this matters. The two-pointer in-place rewrite (read scans, write commits) is the backbone of most O(1)-space array-editing problems.

Return true if s is a subsequence of t (delete some chars of t without reordering to get s). s="abc", t="ahbgdc" → true.

Pattern: two pointers, one per string. Family: sequence matching / merge-style scans.

Practice: LeetCode 392↗ — Is Subsequence.

The approach. Pointer i on s, j on t. Always advance j. Advance i only when s[i]==t[j]. Because a subsequence preserves order, matching greedily as early as possible is always safe. s is a subsequence exactly when i reaches the end of s. Single pass, O(max(m,n)) time, O(1) space.

public boolean isSubsequence(String s, String t) {
    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
        if (s.charAt(i) == t.charAt(j)) i++;   // advance s only on match
        j++;                                   // advance t every step
    }
    return i == s.length();                    // consumed all of s?
}

Edge cases. Empty s → true (0 reaches length 0). s longer than t → loop ends with i < m → false. Equal strings → true.

Interview follow-up. If you must answer many queries s₁, s₂, ... against the same t, preprocess t into per-letter sorted index lists and binary-search each char — O(|t|) prep, O(|s| log |t|) per query. (Raised as the natural scaling variant.) [+]

Why this matters. The "advance both, gate one" two-pointer scan generalizes to merging sorted lists, matching, and interval sweeps.

Return the length of the longest subsequence common to text1 and text2. "abcde", "ace" → 3.

Pattern: two-sequence DP. Family: edit-distance / sequence-alignment DP (siblings: Edit Distance, Shortest Common Supersequence).

Practice: LeetCode 1143↗ — Longest Common Subsequence.

Brute force. Compare from the ends. If last chars match, that char is in the LCS: 1 + LCS(n-1, m-1). If not, drop the last char of one string or the other and take the better: max(LCS(n-1,m), LCS(n,m-1)). Plain recursion recomputes the same (n,m) subproblems exponentially.

The leap. Only two parameters change across calls: the two prefix lengths n and m. That means at most m×n distinct subproblems → memoize on (n,m). Recursion + memoization = dynamic programming. Result: O(m·n) time and space.

int lcsDP(String s1, String s2, int n, int m, Map<String,Integer> memo) {
    if (n == 0 || m == 0) return 0;             // empty prefix -> 0

    String key = n + "," + m;                   // unique per subproblem
    if (memo.containsKey(key)) return memo.get(key);

    int lcs;
    if (s1.charAt(n - 1) == s2.charAt(m - 1)) { // last chars match
        lcs = 1 + lcsDP(s1, s2, n - 1, m - 1, memo);
    } else {                                    // drop one char from either
        lcs = Math.max(lcsDP(s1, s2, n - 1, m, memo), lcsDP(s1, s2, n, m - 1, memo));
    }
    memo.put(key, lcs);
    return lcs;
}

public int longestCommonSubsequence(String text1, String text2) {
    Map<String,Integer> memo = new HashMap<>();
    return lcsDP(text1, text2, text1.length(), text2.length(), memo);
}

Edge cases. No common chars → 0. One string empty → 0. Identical strings → the shorter length.

Interview follow-ups. Convert to a bottom-up int[n+1][m+1] table, then space-optimize to two rows (O(min(m,n)) space). [+] To recover the actual subsequence (not just length), backtrack through the table. The identical recurrence with a cost twist solves Edit Distance.

Why this matters. This is the template for all two-string DP: define state as the two prefix lengths, branch on match vs. mismatch, memoize.

Find the length of the longest substring (contiguous) with all distinct characters. "pwwkew" → 3 ("wke").

Pattern: sliding window with two pointers. Family: variable-size window on a "constraint holds" invariant.

Practice: LeetCode 3↗ — Longest Substring Without Repeating Characters.

Brute force. Check every substring for uniqueness — O(n²) substrings × O(n) check = O(n³). The insight: a window that's already valid only becomes invalid when a duplicate enters, so you never need to restart from scratch.

The leap. Maintain window [i..j]. Expand the right edge j while the window stays all-unique; when a duplicate appears, advance the left edge i until it's unique again. Each pointer only moves forward, so total work is O(n). The uniqueness test: track chars in a map and check mapSize == j - i + 1 — if distinct count equals window width, every char in the window is unique.

Recommended (last-index jump) — the cleanest correct version [+]:

public int lengthOfLongestSubstring(String s) {
    Map<Character,Integer> lastIndex = new HashMap<>();
    int i = 0, max = 0;                       // i = left edge
    for (int j = 0; j < s.length(); j++) {    // j = right edge
        char c = s.charAt(j);
        if (lastIndex.containsKey(c)) i = Math.max(i, lastIndex.get(c) + 1);  // jump past duplicate
        lastIndex.put(c, j);
        max = Math.max(max, j - i + 1);
    }
    return max;
}

Map-size invariant version — keep the [!] caveat above in mind:

public int lengthOfLongestSubstring(String s) {
    Map<Character,Integer> map = new HashMap<>();
    int i = 0, j = 0, max = 0;
    while (j < s.length()) {
        map.put(s.charAt(j), map.getOrDefault(s.charAt(j), 0) + 1);
        if (map.size() == j - i + 1) {          // all unique -> record + grow
            max = Math.max(max, j - i + 1);
            j++;
        } else if (map.size() < j - i + 1) {    // duplicate -> shrink left
            while (map.size() < j - i + 1) {
                map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
                if (map.get(s.charAt(i)) == 0) map.remove(s.charAt(i));
                i++;
            }
            j++;
        }
    }
    return max;
}

Edge cases. Empty string → 0. All-same ("aaaa") → 1. All-unique → full length.

Why this matters. Variable-size sliding window — grow right while a constraint holds, shrink left when it breaks — solves a huge class: min window substring, longest substring with k distinct, max consecutive ones after flips.

Return true if t is an anagram of s (same multiset of letters). Lowercase only. "anagram", "nagaram" → true.

Pattern: fixed-alphabet frequency array. Family: counting / hashing on a bounded charset.

Practice: LeetCode 242↗ — Valid Anagram.

Brute force. Sort both strings and compare — O(n log n). Fine, but you can do linear with counting.

The leap. If lengths differ, immediately false. Otherwise use one int[26]: increment for each char of s, decrement for each char of t. If the strings are anagrams every bucket returns to 0. Single alphabet-bounded array, one increment pass and one decrement pass.

public boolean isAnagram(String s, String t) {
    int m = s.length(), n = t.length();
    if (m != n) return false;                 // different lengths -> not anagram
    int[] count = new int[26];                // lowercase a..z
    for (int i = 0; i < m; i++) count[s.charAt(i) - 'a']++;
    for (int i = 0; i < n; i++) count[t.charAt(i) - 'a']--;
    for (int x : count) if (x != 0) return false;
    return true;
}

Edge cases. Both empty → true. Unequal lengths → false immediately. Same letters, different order → true.

Interview follow-ups. Unicode input → switch to HashMap<Character,Integer>. "Group anagrams" → use the sorted string or the frequency signature as a map key. [+]

Why this matters. The bounded-alphabet counting array (and its +/- cancellation trick) recurs across anagram, permutation-in-string, and character-frequency problems.

The through-line worth returning to: a string is an array of characters, so every array technique — two pointers, in-place index rewriting, sliding window, frequency counting — carries over. When a bounded charset is stated, use a fixed-size array for O(1) space. When brackets or precedence appear, reach for a stack. When two indices vary in a recurrence, it's 2D DP. And when order + "smallest/largest" appear together, reach for a monotonic stack.