Arrays & Strings

Arrays and strings are the highest-frequency category in coding interviews and the one candidates most often underestimate. The questions look mechanical — remove a character, reverse the words, check an anagram — but each one hides a decision about how you represent the data and which pointer discipline you use to walk it. This session systematizes the whole family: the char[] mindset behind immutable strings, the slow/fast in-place compaction pattern, the reverse-the-whole-then-reverse-the-parts identity, frequency counting for anagrams and permutations, and the sliding window that powers half of all substring questions.

Foundations: char[], Immutability, and Two Kinds of Pointer

Before any specific problem, the session sets up how data gets represented. How do you represent a number? You can use an array, a string, or a linked list — and a linked list is the friendliest for add/subtract/multiply/divide, because you can prepend a carry digit in O(1). The classic framing: "123" stored digit-by-digit as 3 → 2 → 1 → null, and a leading-zero input like "00456" needs a preprocessing pass before you trust it.

For strings specifically, three facts drive every decision. First, a Java string is immutable and implemented by a char[]. Second, substring(start, end) is O(n) — it allocates a brand-new string over the half-open range [start, end), so it is not free. Third, s1 + s2 is O(m + n), and inside a loop that quietly becomes O(n²). The escape hatch is StringBuilder (append, insert, deleteCharAt, charAt, toString), whose amortized append is O(1). Two conversions are worth muscle memory: str.toCharArray() going in, and new String(ca, start, len) or String.valueOf(ca) coming back out.

That immutability is exactly why two pointers is the dominant technique here. There are two shapes, and picking the right one is half the battle:

• slow / fast — both move in the same direction. fast reads and explores, slow writes the answer. This compacts an array in place: removal, dedup, space normalization.
• left / right — the two ends converge toward the middle. This reverses, rotates, and checks palindromes.

In-Place Removal with Slow/Fast Pointers

The purest slow/fast problem: remove every occurrence of a character — e.g. delete 'f' and 'o' from "yougetoffer". Two clean options: build the result with a StringBuilder in one pass (append only when the char is a keeper), or convert to char[] and let fast read while slow writes. The array version is the one to internalize because it introduces the invariant every removal problem shares.

public String removeChar(String s, char c) {
    if (s == null || s.length() == 0) return s;
    char[] ca = s.toCharArray();
    int slow = 0;
    for (int fast = 0; fast < s.length(); fast++) {
        if (ca[fast] != c) {          // keep chars we want, drop the rest
            ca[slow++] = ca[fast];
        }
    }
    return new String(ca, 0, slow);   // [0, slow) is the compacted answer
}

A variant worth knowing: if order does not matter, you can instead swap the unwanted char to the far end and shrink the boundary. It is still O(n) but not stable — the surviving elements get reordered. That is exactly the optimal answer to LC 27 Remove Element when the problem does not require preserving order.

Deduplicate a Sorted Array — Keep k Copies

Same skeleton, different comparison. To remove duplicates from a sorted array while keeping at most k copies of each value, compare ca[fast] against ca[slow - k]: if they differ, this element earns a slot. Start both pointers at k. One parameter unifies two famous problems — LC 26 (keep one, k = 1) and LC 80 (keep two, k = 2) — and the "compare fast with slow − k" trick is what makes it generalize.

Normalize Spaces

Collapse leading, trailing, and duplicated spaces down to a single space between words: "␣␣␣you␣␣␣get␣offer␣␣" becomes "you␣get␣offer". The slow/fast loop skips a space whenever it is leading or immediately follows another space (ca[fast] == ' ' && (fast == 0 || ca[fast-1] == ' ') → skip). One post-processing step remains: the result may end in a single trailing space, so drop it if present. This tiny helper — call it removeDuplicateSpaces — reappears verbatim inside the reverse-words problem below.

The Reversal Family

Reverse a string (LC 344) is the canonical left/right problem: swap(ca, i++, j--) until the pointers meet. It also makes a nice recursion drill — you can write it as tail recursion (swap, then recurse inward) or as pre/post-order recursion, but watch the trap the notes flag: if you mutate i and j before recursing, you must restore them afterward, because the same array is shared across the call stack.

LC 151 Reverse Words in a String ("you get offer" → "offer get you") has three angles. The quickest to write uses split(" "), then rebuilds with a StringBuilder in reverse order — but beware that multiple spaces make split emit empty tokens, so you must skip "" entries. The angle that impresses is the O(1)-extra-space triple move: reverse the entire char array, then reverse each word back, then squeeze the spaces. Two pointers find each word boundary, and the last word needs a final reverse because there is no trailing space to trigger it.

public String reverseWords(String s) {
    if (s == null || s.length() == 0) return "";
    char[] ca = s.toCharArray();
    reverse(ca, 0, ca.length - 1);      // 1. reverse the whole sentence
    int i = 0, j;
    for (j = 0; j < ca.length; j++) {   // 2. reverse each word back
        if (ca[j] == ' ') {
            reverse(ca, i, j - 1);
            i = j + 1;
        }
    }
    reverse(ca, i, j - 1);              // last word has no trailing space to trigger it
    return removeDuplicateSpaces(ca);       // 3. collapse extra spaces
}

private void reverse(char[] ca, int i, int j) {
    while (i < j) {
        char t = ca[i]; ca[i] = ca[j]; ca[j] = t;
        i++; j--;
    }
}

The third angle is a special pattern: some inputs treat a multi-word phrase as one token — "Let's go to new york" → "new york to go Let's", where "new york" stays intact. Same recipe: global reverse, then locally reverse using markers to delimit tokens, with post-processing on the final token.

String rotation / shift ("abcdefg" → "efgabcd") is the exact same identity. Take offset %= n first, then apply three reversals: reverse [0, n-offset-1], reverse [n-offset, n-1], reverse the whole thing. Rotate-by-triple-reverse and reverse-words are the same trick wearing different clothes.

Encode, Decode, and String Math

This cluster is about turning characters into structured output and back. Run-length encoding — "aaabbbbccdeee" → "a3b4c2d1e3" — is a single scan with a run counter that flushes char + count whenever the character changes. LC 38 Count and Say is run-length encoding applied recursively: each row is built by run-length describing the previous row. Walk the previous string, count consecutive equal chars, and append count then char on each change (plus one final flush after the loop). The notes also file LC 191 here as an encode/decode-adjacent drill.

LC 8 String to Integer (atoi) is the math workhorse: skip leading spaces, read an optional +/- sign, then accumulate digits — and the whole difficulty is overflow. Guard before you multiply: if (Integer.MAX_VALUE - digit) / 10 < total, clamp to MAX_VALUE or MIN_VALUE by sign instead of letting total = 10 * total + digit wrap around. This check-before-you-grow discipline is the interview point.

URL space replacement (LintCode's Space Replacement) maps ' ' ↔ "%20". Because "%20" is longer than a space, the clean in-place approach is to count the spaces first, then write from the back, so you never overwrite a character you have not read yet. That "fill from the end" idea is the same one behind in-place array merges.

Pattern Matching: strStr and DP Matching

LC 28 Implement strStr() — find the first index where needle occurs in haystack. Remember that in Java substring is O(n), so slicing to compare is wasteful; scan by index instead. The naive double loop is O(m·n), but the outer pointer only needs to run to n − m (past that, needle cannot fit).

public int strStr(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();   // cache the lengths
    for (int i = 0; i <= n - m; i++) {                 // stop at n - m, needle can't fit past it
        int j;
        for (j = 0; j < m; j++) {
            if (haystack.charAt(i + j) != needle.charAt(j)) break;
        }
        if (j == m) return i;                          // matched all of needle
    }
    return -1;
}

The upgrade is Rabin-Karp: keep a rolling hash of the current window, and on each step subtract the char sliding out and add the char sliding in — one hash comparison per position, O(n − m + 1 + m) = O(n). The caveat to volunteer: long patterns risk hash collisions, so compare lengths first, then the hash, then verify character-by-character on a hit. The same scan also generalizes from String to a linked list (walk with .next and size()) or to searching for multiple needles at once.

The two hardest problems in the set are DP matchers where dp[i][j] answers "does s[0..i) match p[0..j)?" LC 44 Wildcard Matching: '?' matches exactly one char (dp[i][j] = dp[i-1][j-1]), and '*' matches empty or one-more (dp[i][j] = dp[i][j-1] || dp[i-1][j]); initialize the top row so a run of '*' can match the empty string. LC 10 Regular Expression Matching is trickier because '*' binds to the preceding character: "a*" can count as empty (dp[i][j-2]) or, when the current char matches a or the pattern is '.', extend the match (dp[i-1][j]). Recognizing the state definition is the whole game; once dp[i][j] is nailed down the transitions are casework.

Permutations

LC 46 Permutations (no duplicates) is swap-based DFS: at each level, for i from level to n-1, swap i into level, recurse on level + 1, then swap back. Why the swap back? Because Java passes the array by reference-value — the recursion mutates the same array, so you must restore it (classic backtracking). If instead you built a fresh string at each level, there would be nothing to undo.

LC 47 Permutations II (with duplicates) sorts first so equal values sit adjacent, then dedupes choices. Two ways: a per-level HashSet that rejects a value already tried at this position, or a used[] boolean array with the classic skip rule. The subtlety of the boolean version: you only skip a duplicate whose identical predecessor is not yet used in the current path — that keeps exactly one ordering of each equal block, because a checkbox that merely detects duplication cannot also tell you which copy was already consumed.

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    Arrays.sort(nums);                       // group equal values together
    backtrack(res, new ArrayList<>(), nums, new boolean[nums.length]);
    return res;
}

private void backtrack(List<List<Integer>> res, List<Integer> temp,
                       int[] nums, boolean[] used) {
    if (temp.size() == nums.length) {
        res.add(new ArrayList<>(temp));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // skip a duplicate whose identical predecessor is not yet used on this path
        if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
        used[i] = true;
        temp.add(nums[i]);
        backtrack(res, temp, nums, used);
        used[i] = false;                     // undo — the array is shared
        temp.remove(temp.size() - 1);
    }
}

Anagram, Palindrome, and Isomorphic

LC 242 Valid Anagram is the frequency-array poster child: walk the first string incrementing an int[26], walk the second decrementing it, then confirm every bucket is zero. O(n) time, O(1) space (26, 52, 128, or 256 depending on the alphabet). Compare lengths first as a fast reject, or catch a negative bucket mid-loop. Alternatives from the notes: sort both and compare (O(n log n)), or a base-26 char hash — but 26 copies of a collide with a single b, so a raw polynomial hash needs an auxiliary check like comparing lengths. When the question becomes "find all anagrams of a pattern inside a string" (LC 438), the recipe is sliding window + char hashing: a fixed-width window whose frequency table you match against the pattern's.

LC 125 Valid Palindrome is left/right convergence: skip non-alphanumeric characters on either end, lowercase, and compare. The one-liner alternative — replaceAll("[^A-Za-z0-9]", "").toLowerCase() then compare to its reverse — reads cleanly but pays O(n) extra space for two throwaway strings.

LC 5 Longest Palindromic Substring flips the direction: expand around center. For each index, try an odd center (i, i) and an even center (i, i+1), extending outward while the two ends match. After the while overshoots, the palindrome length is k - j - 1 — mind that off-by-one, because j and k have each stepped one past the valid boundary. O(n²) time, O(1) space; Manacher's is the O(n) follow-up but is rarely required.

LC 205 Isomorphic Strings looks like a single-map problem and is not: a lone map char → char fails because the mapping must be a bijection — two source chars must not collapse onto the same target. Use two maps (or map each char to its last-seen index and compare those indices) to enforce both directions.

LC 9 Palindrome Number proves you do not need a string at all: reverse only half the digits. Loop while (x > rev) building rev = rev*10 + x%10 and shrinking x /= 10; handle the trailing-zero trap up front (x != 0 && x % 10 == 0 → not a palindrome, since the reverse would gain a leading zero), and return x == rev || x == rev/10 to cover even- and odd-length numbers.

Sliding Window on Strings

Two signals betray a sliding-window problem: the word "substring", and a superlative — "longest" or "shortest such that…". The mechanics are always the same: the fast pointer marches forward unconditionally, [slow, fast] is maintained as a valid window, and membership/repeat checks stay O(1) via a HashSet or HashMap.

LC 3 Longest Substring Without Repeating Characters keeps a HashMap of each character's most recent index. On a repeat, jump slow to max(slow, lastIndex + 1) — the max matters, because a stale index sitting behind the current slow must not drag the window backwards. A HashMap beats a HashSet here precisely because it carries the index, so slow can leap instead of crawling one step at a time.

public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0) return 0;
    HashMap<Character, Integer> map = new HashMap<>();
    int max = 0;
    for (int fast = 0, slow = 0; fast < s.length(); fast++) {
        char c = s.charAt(fast);
        if (map.containsKey(c)) {
            slow = Math.max(slow, map.get(c) + 1);   // jump past the old copy, never backwards
        }
        map.put(c, fast);
        max = Math.max(max, fast - slow + 1);        // [slow, fast] is repeat-free
    }
    return max;
}

The "at most k repeating chars" variant swaps the invalidation rule: when some character's count exceeds k, crawl slow forward, decrementing counts in the map, until that character is back within budget. Same window skeleton, different shrink trigger.

LC 76 Minimum Window Substring is the boss of the family: find the shortest window of s containing all of t. Build a need-count map for t plus a count of satisfied requirements; expand right until the window covers t (count == t.length()), then contract left while it still covers, recording the minimum each time.

public String minWindow(String s, String t) {
    HashMap<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray())
        need.put(c, need.getOrDefault(c, 0) + 1);

    int left = 0, minLeft = 0, minLen = s.length() + 1, count = 0;
    for (int right = 0; right < s.length(); right++) {
        char r = s.charAt(right);
        if (need.containsKey(r)) {
            need.put(r, need.get(r) - 1);
            if (need.get(r) >= 0) count++;     // only count still-needed chars
        }
        while (count == t.length()) {           // window covers t → try to shrink
            if (right - left + 1 < minLen) {
                minLeft = left;
                minLen = right - left + 1;
            }
            char l = s.charAt(left);
            if (need.containsKey(l)) {
                need.put(l, need.get(l) + 1);
                if (need.get(l) > 0) count--;   // dropped a char we actually needed
            }
            left++;
        }
    }
    return minLen == s.length() + 1 ? "" : s.substring(minLeft, minLeft + minLen);
}

Problem Checklist