DSA Series: String (Blind 75, Java)

Overview

• Pattern cheat-sheet
• 1. Longest Substring Without Repeating Characters (Medium · LeetCode #3)
• 2. Longest Repeating Character Replacement (Medium · LeetCode #424)
• 3. Minimum Window Substring (Hard · LeetCode #76)
• 4. Valid Anagram (Easy · LeetCode #242)
• 5. Group Anagrams (Medium · LeetCode #49)
• 6. Valid Parentheses (Easy · LeetCode #20)
• 7. Valid Palindrome (Easy · LeetCode #125)
• 8. Longest Palindromic Substring (Medium · LeetCode #5)
• 9. Palindromic Substrings (Medium · LeetCode #647)
• 10. Encode and Decode Strings (Medium · LeetCode #271 · Premium)

Part of the DSA Blind 75 series. Track your progress on the Interview Prep page.

Java 11+. All code in this file was compiled and tested with asserts (examples, edge cases, and randomized checks against brute force for substring/palindrome problems).

Pattern cheat-sheet

Sliding window (variable size) - for "longest/shortest substring satisfying a condition".

int left = 0;
for (int right = 0; right < n; right++) {
    add(s[right]);                       // expand
    while (windowInvalid()) {            // shrink until valid (or for "min window": while valid)
        remove(s[left]); left++;
    }
    best = Math.max(best, right - left + 1);
}

• "Longest valid" -> shrink while invalid. "Shortest valid" -> record answer while valid, then shrink.
• State is usually int[26]/int[128] or HashMap<Character,Integer>.

Two pointers - opposite ends (palindrome check) or expand-from-center (palindromic substrings).

Fast/slow, dummy node - linked-list tools; in strings, the analogue is read/write pointers for in-place edits.

Hashing by signature - map each item to a canonical key (sorted chars, or 26-count vector) so equivalent items collide in a HashMap<String, List<String>>.

Stack - nested/matching structures (parentheses, JSON/XML tags).

Length-prefix framing - encode variable-length strings safely with len#payload.

1. Longest Substring Without Repeating Characters (Medium · LeetCode #3)

Problem statement. Given a string s, return the length of the longest substring with no repeated characters.

• "abcabcbb" -> 3 ("abc"); "bbbbb" -> 1; "pwwkew" -> 3 ("wke"); "" -> 0.
• Constraints: 0 <= s.length <= 5*10^4; s has letters, digits, symbols, spaces.

How the interviewer asks / follow-ups.

• Disguise: "Given a stream of transaction IDs/device fingerprints, find the longest run of consecutive events with all-distinct merchant IDs" (fraud velocity windows).
• Follow-ups: return the substring itself (track start index)? Unicode / emoji (surrogate pairs - iterate code points)? Streaming input (window state only)? At most k distinct characters (LC 340)? Why must left never move backwards (the abba case)?
• Evaluating: sliding window, hashmap of last index, handling the stale-index trap.

Approach 1: Brute force. For every start i, extend j until a repeat (using a HashSet), track max. Time O(n * min(n, Σ)) - worst O(n^2); space O(min(n, Σ)). (Fully naive checking every substring is O(n^3).)

Approach 2: Sliding window with a set. Expand right; while s[right] is in the set, remove s[left++]. Time O(n) (each char added and removed once), space O(min(n, Σ)).

Approach 3: Sliding window with last-seen index (optimal). Intuition: instead of shrinking one at a time, jump left directly past the previous occurrence: left = max(left, last[c] + 1). Trace "abba": r=0 a (left 0, len1); r=1 b (len2); r=2 b, last[b]=1 -> left=2 (len1); r=3 a, last[a]=0 < left so ignore (the stale-index trap) -> len = 3-2+1 = 2. Answer 2.

Java code.

static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> last = new HashMap<>(); // char -> most recent index
    int best = 0, left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        Integer prev = last.get(c);
        if (prev != null && prev >= left) left = prev + 1; // only if inside current window
        last.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Complexity.

• Brute: Time O(n^2) worst case, Space O(min(n, Σ)).
• Set window: Time O(n), Space O(min(n, Σ)) - each index enters and leaves at most once.
• Last-index map: Time O(n), Space O(min(n, Σ)) - single pass; Σ is alphabet size (use int[128] for ASCII to get a flat O(1)).

Edge cases / pitfalls.

• Empty string -> 0; single char -> 1.
• The prev >= left check (otherwise "abba" returns 3).
• Chars outside ASCII: a char-keyed map works for BMP; emojis are surrogate pairs - use codePoints() if exact characters matter.
• Substring vs subsequence ("pwke" is not a substring).

Pattern & related problems. Variable sliding window. Related: Longest Repeating Character Replacement (424), Minimum Window Substring (76), Longest Substring with At Most K Distinct Characters (340), Fruit Into Baskets (904), Subarrays with K Different Integers (992).

2. Longest Repeating Character Replacement (Medium · LeetCode #424)

Problem statement. Given an uppercase string s and integer k, you may replace at most k characters with any uppercase letter. Return the length of the longest substring of identical letters you can obtain.

• s="ABAB", k=2 -> 4; s="AABABBA", k=1 -> 4 ("AABA" -> "AAAA").
• Constraints: 1 <= s.length <= 10^5, s uppercase English, 0 <= k <= s.length.

How the interviewer asks / follow-ups.

• Disguise: "A day's status codes (S/F/P...) - the longest stretch that could be made uniformly SUCCESS if we may correct up to k bad records" (data-quality repair budget).
• Follow-ups: why is maxFreq allowed to be stale (never decreased)? Lowercase + uppercase / arbitrary Unicode (use a HashMap, and exact max recompute is O(Σ))? Return the actual substring? Related: max consecutive ones III (1004).
• Evaluating: the window validity formula len - maxFreq <= k and the insight about non-shrinking window.

Approach 1: Brute force. For every substring compute its most frequent char; valid if len - maxFreq <= k. Time O(n^2) with incremental counts (O(n^3) naive), space O(26).

Approach 2: Window + recompute max each time. Window is valid iff len - maxCount <= k (we replace everything but the majority letter). Slide; when invalid shrink left by one. Recomputing maxCount from 26 counters costs O(26 n) = O(n). Fine.

Approach 3: Window with non-decreasing maxFreq (optimal trick). Intuition: the answer only grows when we find a window with a higher max frequency than ever seen, so we never need to lower maxFreq on shrink. A stale (too large) maxFreq can only make the window look valid when it is not, but such a window is never longer than the best already recorded, so the answer is unaffected. The window slides (grows by 1 or shifts) rather than shrinking, so its size never decreases. Trace "AABABBA", k=1: window grows to AAB (len3, maxF 2, 3-2=1 ok), AABA (len4, maxF 3, 1 ok), then add B: len5, maxF 3, 5-3=2>1 -> drop left (slide, len stays 4); continues; final best 4.

Java code.

static int characterReplacement(String s, int k) {
    int[] cnt = new int[26];
    int left = 0, maxFreq = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        maxFreq = Math.max(maxFreq, ++cnt[s.charAt(right) - 'A']); // only ever increases
        if ((right - left + 1) - maxFreq > k) {   // need more than k replacements
            cnt[s.charAt(left) - 'A']--;          // slide window: drop one from left
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

(Using if rather than while is intentional: the window never needs to shrink by more than one per step.)

Complexity.

• Brute: Time O(n^2), Space O(26).
• Window with recomputed max: Time O(26·n), Space O(26).
• Window with stale maxFreq: Time O(n), Space O(1) - one pass, constant-size counter array.

Edge cases / pitfalls.

• k = 0 (reduces to longest run of equal chars).
• k >= n (answer is n).
• Explain why not decreasing maxFreq is safe - interviewers probe this.
• Counters indexed with - 'A'; for mixed case or Unicode use a map.

Pattern & related problems. Variable sliding window with a budget. Related: Max Consecutive Ones III (1004), Longest Substring with At Most K Distinct (340), Longest Substring Without Repeating Characters (3), Frequency of the Most Frequent Element (1838).

3. Minimum Window Substring (Hard · LeetCode #76)

Problem statement. Given strings s and t, return the smallest substring of s that contains every character of t (with multiplicity); return "" if none.

• s="ADOBECODEBANC", t="ABC" -> "BANC"; s="a", t="a" -> "a"; s="a", t="aa" -> "".
• Constraints: 1 <= |s|,|t| <= 10^5; English letters. Follow-up: O(|s|+|t|).

How the interviewer asks / follow-ups.

• Disguise: "Given an event log string/stream and a set of required event types (e.g. AUTH, FRAUD_CHECK, CAPTURE), find the shortest contiguous slice of the log containing all of them" (smallest audit window).
• Follow-ups: streaming (can't re-read) - keep the window buffered; t huge or Unicode (HashMap); required order (becomes subsequence, LC 727); return all minimal windows; many queries on the same s (preprocess positions per char).
• Evaluating: the expand/contract template, the missing counter trick, avoiding O(|alphabet|) checks per step.

Approach 1: Brute force. Enumerate all substrings, check coverage by counting. Time O(n^2 * m) (or O(n^3)), space O(Σ).

Approach 2: Sliding window with need-counts (optimal). Intuition: expand right until the window covers t; then shrink left as far as possible while it still covers t, recording the best; continue. Maintain need[c] = how many more of char c we need (can go negative = surplus) and missing = total characters still unmet. A character decrements missing only when need[c] was positive before decrement. Trace s="ADOBECODEBANC", t="ABC": expand to "ADOBEC" (missing 0, len 6). Shrink: drop A -> missing 1. Expand ... "CODEBA" (len 6) ... then "BANC" (len 4) is the minimum; shrinking beyond breaks coverage. Answer "BANC".

Java code.

static String minWindow(String s, String t) {
    if (t.isEmpty() || s.length() < t.length()) return "";
    int[] need = new int[128];                  // ASCII; use a HashMap for full Unicode
    for (char c : t.toCharArray()) need[c]++;
    int missing = t.length();                   // total chars still required
    int left = 0, bestStart = 0, bestLen = Integer.MAX_VALUE;
    for (int right = 0; right < s.length(); right++) {
        if (need[s.charAt(right)]-- > 0) missing--; // was needed -> now satisfied
        while (missing == 0) {                      // window covers t: try to shrink
            if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
            if (++need[s.charAt(left)] > 0) missing++; // removing a needed char breaks coverage
            left++;
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

Complexity.

• Brute: Time O(n^2·m) or worse, Space O(Σ).
• Sliding window: Time O(|s|+|t|) - each index enters and leaves the window once, O(1) per step thanks to missing; Space O(Σ) (128 here, O(1)).

Edge cases / pitfalls.

• t longer than s -> ""; duplicates in t ("aa") must be matched with multiplicity.
• Using a set of required chars instead of counts is wrong.
• The need[c]-- > 0 check (post-decrement compare) is the subtle bit.
• Non-ASCII input would index out of bounds in int[128]; switch to a map.
• Ties: this returns the leftmost minimal window.

Pattern & related problems. Variable sliding window (shrink while valid). Related: Permutation in String (567), Find All Anagrams in a String (438), Substring with Concatenation of All Words (30), Minimum Size Subarray Sum (209), Minimum Window Subsequence (727).

4. Valid Anagram (Easy · LeetCode #242)

Problem statement. Return true if t is an anagram of s (same letters, same counts, any order).

• "anagram","nagaram" -> true; "rat","car" -> false.
• Constraints: 1 <= |s|,|t| <= 5*10^4, lowercase English. Follow-up: Unicode?

How the interviewer asks / follow-ups.

• Disguise: "Do these two reference/token strings contain the same characters (e.g. checking if two scrambled card-token fragments or merchant names are permutations)?"
• Follow-ups: Unicode input (use a HashMap of code points, beware surrogate pairs and normalization - NFC vs NFD)? Case-insensitive / ignoring spaces? Streams of characters (single counter map)? Compare against a million candidates (see Group Anagrams signature)?
• Evaluating: counting vs sorting trade-offs; early exit on length mismatch.

Approach 1: Brute force / sorting. Sort both char arrays and compare. Time O(n log n), space O(n) (copying char arrays).

Approach 2: Frequency count (optimal). Intuition: anagrams have identical letter histograms. One array: increment for s, decrement for t; everything must return to zero. Trace "rat" vs "car": r:+1-... after loop counts: a: +1-1=0, t:+1, c:-1, r: +1-1=0 -> non-zero -> false.

Java code.

static boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false; // quick reject
    int[] cnt = new int[26];
    for (int i = 0; i < s.length(); i++) {
        cnt[s.charAt(i) - 'a']++;
        cnt[t.charAt(i) - 'a']--;
    }
    for (int c : cnt) if (c != 0) return false;
    return true;
}

// Follow-up: arbitrary Unicode (code points, handles emojis/surrogate pairs)
static boolean isAnagramUnicode(String s, String t) {
    Map<Integer, Integer> m = new HashMap<>();
    s.codePoints().forEach(cp -> m.merge(cp, 1, Integer::sum));
    t.codePoints().forEach(cp -> m.merge(cp, -1, Integer::sum));
    for (int v : m.values()) if (v != 0) return false;
    return true;
}

Complexity.

• Sorting: Time O(n log n), Space O(n) (or O(log n) with in-place sort on copies).
• Count array: Time O(n), Space O(1) - fixed 26 slots.
• Unicode map: Time O(n), Space O(k) distinct code points.

Edge cases / pitfalls.

• Different lengths; identical strings (still an anagram).
• Uppercase/non-letter chars would break - 'a' indexing - confirm the alphabet.
• Unicode normalization ("é" as one code point vs e + combining accent) - mention java.text.Normalizer.

Pattern & related problems. Frequency counting / hashing. Related: Group Anagrams (49), Find All Anagrams in a String (438), Permutation in String (567), Ransom Note (383).

5. Group Anagrams (Medium · LeetCode #49)

Problem statement. Group the strings in an array that are anagrams of each other; any order of groups and within groups.

• ["eat","tea","tan","ate","nat","bat"] -> [["bat"],["nat","tan"],["ate","eat","tea"]]; [""] -> [[""]]; ["a"] -> [["a"]].
• Constraints: 1 <= N <= 10^4, 0 <= len <= 100, lowercase.

How the interviewer asks / follow-ups.

• Disguise: "Cluster merchant names / narration strings that are character permutations to spot duplicate or scrambled entries," or "bucket incoming tokens by canonical form."
• Follow-ups: avoid sorting (count signature)? Key collision risk (why use "a1b2"-style key with separators rather than concatenated counts like "121")? Huge dataset (partition by signature hash - MapReduce style)? Unicode (sorted code points or map keys)?
• Evaluating: hashing-by-signature idea, key design, complexity in N and K.

Approach 1: Brute force. For each string, compare with every group representative using isAnagram. Time O(N^2 * K), space O(N K).

Approach 2: Sorted string as key. Sort each word's chars; use as map key. Time O(N K log K), space O(N K).

Approach 3: Count signature as key (optimal for long words). Intuition: the 26-count histogram is the canonical form; serialize as a1e1t1. Strings with the same signature go in the same bucket. Trace "eat" -> a1e1t1; "tea" -> a1e1t1; "tan" -> a1n1t1; buckets: {a1e1t1: [eat,tea,ate], a1n1t1: [tan,nat], a1b1t1: [bat]}.

Java code.

static List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        StringBuilder sb = new StringBuilder();           // unambiguous key: letter + count
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) sb.append((char) ('a' + i)).append(cnt[i]);
        }
        groups.computeIfAbsent(sb.toString(), x -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

(Sort-key variant: char[] a = s.toCharArray(); Arrays.sort(a); String key = new String(a);)

Complexity.

• Brute: Time O(N^2·K), Space O(N·K).
• Sorted key: Time O(N·K log K), Space O(N·K) - sorting each of N words of length K.
• Count key: Time O(N·(K+26)) = O(N·K), Space O(N·K) - histogram per word, key length bounded by 26 entries.

Edge cases / pitfalls.

• Empty string key "" is valid and groups together.
• Key ambiguity: concatenating raw counts without letters/delimiters ("11" ambiguous) - include the letter, or use a delimiter like #.
• Do not use int[] as a map key (identity hashing); convert to String or List<Integer>.
• Output order is not guaranteed; do not assert on it.

Pattern & related problems. Hashing by signature. Related: Valid Anagram (242), Group Shifted Strings (249), Find Duplicate File in System (609), Isomorphic Strings (205).

6. Valid Parentheses (Easy · LeetCode #20)

Problem statement. Given a string of ()[]{}, determine whether brackets are closed by the same type and in the correct order.

• "()[]{}" -> true; "(]" -> false; "([)]" -> false; "{[]}" -> true.
• Constraints: 1 <= |s| <= 10^4.

How the interviewer asks / follow-ups.

• Disguise: "Validate that a JSON / XML / ISO 8583-style nested message or a templated expression is well-formed" or "check that begin/commit/rollback markers in a transaction log nest properly."
• Follow-ups: other characters in the string (ignore them); report the position of the first error; XML tags with names (stack of tag strings); streaming input of unbounded size (stack depth is the memory); minimum insertions/removals to fix (LC 921/1249); only one bracket type (counter suffices, O(1) space); concurrency/size limits (reject if depth > limit).
• Evaluating: stack as the natural structure, early exits, clean handling of unmatched closers.

Approach 1: Brute force. Repeatedly delete adjacent matched pairs (), [], {} until no change; valid if empty. Time O(n^2), space O(n) (new strings).

Approach 2: Stack (optimal). Intuition: the most recently opened bracket must be the first closed (LIFO). On an opener push the expected closer; on a closer, pop and compare. Trace "([)]": push ), push ]; read ) -> pop ] != ) -> false. Trace "{[]}": push }, push ], read ] pops ], read } pops } -> stack empty -> true.

Java code.

static boolean isValid(String s) {
    if ((s.length() & 1) == 1) return false;       // odd length can never balance
    Deque<Character> st = new ArrayDeque<>();      // prefer ArrayDeque over legacy Stack
    for (char c : s.toCharArray()) {
        switch (c) {
            case '(': st.push(')'); break;         // push the expected closer
            case '[': st.push(']'); break;
            case '{': st.push('}'); break;
            default:                               // a closing bracket
                if (st.isEmpty() || st.pop() != c) return false; // unmatched or wrong type
        }
    }
    return st.isEmpty();                           // leftovers mean unclosed openers
}

(If other characters are allowed, add a case that ignores non-bracket chars and drop the odd-length shortcut.)

Complexity.

• Repeated replace: Time O(n^2), Space O(n).
• Stack: Time O(n) - one pass, O(1) per char; Space O(n) - worst case all openers.

Edge cases / pitfalls.

• Empty string (valid, per the general definition), only closers ("]"), only openers ("((").
• Popping from an empty stack (check isEmpty first).
• Return st.isEmpty(), not true.
• Deque<Character> autoboxing: st.pop() != c compares Character to char and unboxes - fine; avoid comparing two Character objects with !=.

Pattern & related problems. Stack for nesting. Related: Generate Parentheses (22), Longest Valid Parentheses (32), Minimum Remove to Make Valid Parentheses (1249), Valid Parenthesis String (678), Decode String (394), Basic Calculator (224).

7. Valid Palindrome (Easy · LeetCode #125)

Problem statement. After lowercasing and removing non-alphanumeric characters, check whether the string reads the same forward and backward.

• "A man, a plan, a canal: Panama" -> true; "race a car" -> false; " " -> true.
• Constraints: 1 <= |s| <= 2*10^5, printable ASCII.

How the interviewer asks / follow-ups.

• Disguise: "Check whether an account/reference number, ignoring dashes and spaces, is a palindrome" (a mirrored-pattern detector), or sanitize-then-compare input.
• Follow-ups: do it in O(1) extra space (no cleaned copy); Unicode (code points, Character.isLetterOrDigit vs ASCII-only); allow deleting at most one character (LC 680); very long streaming input (two ends needed - can't stream; compare with reversed hash).
• Evaluating: two-pointer discipline and not building unnecessary copies.

Approach 1: Brute force. Build a cleaned lowercase string, reverse it, compare. Time O(n), space O(n).

Approach 2: Two pointers in place (optimal). Intuition: compare from both ends, skipping non-alphanumerics, no extra string. Trace "A man, a plan...": i at A, j at a -> equal (case-insensitive); i skips space to m, j to m... all match -> true. Trace "0P": '0' != 'p' -> false (note digits are compared too).

Java code.

static boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++; // skip junk on the left
        while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--; // skip junk on the right
        if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false;
        i++; j--;
    }
    return true;
}

Complexity.

• Clean + reverse: Time O(n), Space O(n).
• Two pointers: Time O(n) - each index visited once; Space O(1).

Edge cases / pitfalls.

• String of only punctuation (".,") or a single space -> true.
• Inner i < j guards in the skip loops prevent index overflow.
• Digits count as alphanumeric ("0P" is false).
• Character.isLetterOrDigit accepts non-ASCII letters; ask whether ASCII-only is intended. For supplementary code points use codePointAt.

Pattern & related problems. Two pointers from both ends. Related: Valid Palindrome II (680), Palindrome Linked List (234), Longest Palindromic Substring (5), Palindrome Number (9), Reverse String (344).

8. Longest Palindromic Substring (Medium · LeetCode #5)

Problem statement. Return the longest palindromic substring of s.

• "babad" -> "bab" (or "aba"); "cbbd" -> "bb"; "a" -> "a".
• Constraints: 1 <= |s| <= 1000, digits and letters.

How the interviewer asks / follow-ups.

• Disguise: "Find the longest mirrored segment in a transaction-ID or a sequence string" (pattern detection). Often posed generically.
• Follow-ups: can you beat O(n^2) (Manacher's algorithm is O(n))? O(1) space? Return all longest ones? Count of palindromic substrings (next problem)? Longest palindromic subsequence (LC 516, a DP)?
• Evaluating: recognizing center expansion as a simple O(n^2)/O(1) approach, handling odd/even centers, DP awareness.

Approach 1: Brute force. Check every substring for being a palindrome. Time O(n^3), space O(1).

Approach 2: Dynamic programming. dp[i][j] = s[i]==s[j] && (j-i<3 || dp[i+1][j-1]). Time O(n^2), space O(n^2).

Approach 3: Expand around center (optimal practical). Intuition: every palindrome has a center - one of 2n-1 positions (a char for odd length, a gap between chars for even length). Expand outward while characters match; record the longest. Trace "babad": center 1 ('a') expands to bab (len 3) - start = c - (len-1)/2 = 0. Center 2 ('b') gives aba, len 3 (not longer). Answer "bab". Trace "cbbd": even center between the two b's gives len 2, start = 1 - (2-1)/2 = 1 -> "bb". Manacher's algorithm reaches O(n) time and O(n) space by reusing mirrored radii; mention it, but center expansion is what is expected in most interviews.

Java code.

static String longestPalindrome(String s) {
    if (s == null || s.isEmpty()) return "";
    int start = 0, maxLen = 1;
    for (int c = 0; c < s.length(); c++) {
        int odd  = expand(s, c, c);       // center on a character
        int even = expand(s, c, c + 1);   // center between two characters
        int len = Math.max(odd, even);
        if (len > maxLen) {
            maxLen = len;
            start = c - (len - 1) / 2;    // works for both odd and even lengths
        }
    }
    return s.substring(start, start + maxLen);
}

// returns the length of the palindrome grown from (l, r)
private static 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;                     // loop overshot by one on each side
}

Complexity.

• Brute: Time O(n^3), Space O(1).
• DP: Time O(n^2), Space O(n^2).
• Center expansion: Time O(n^2) worst case (e.g. "aaaa..."), Space O(1).
• Manacher: Time O(n), Space O(n).

Edge cases / pitfalls.

• Single char; all identical chars; no palindrome longer than 1 (return first char).
• Forgetting even-length centers ("cbbd").
• Start index formula for even lengths: c - (len-1)/2.
• Avoid substring in the inner loop (creates O(n) copies, making it O(n^3)).

Pattern & related problems. Expand from center / DP on substrings. Related: Palindromic Substrings (647), Longest Palindromic Subsequence (516), Palindrome Partitioning (131), Shortest Palindrome (214).

9. Palindromic Substrings (Medium · LeetCode #647)

Problem statement. Count how many substrings of s are palindromes (substrings at different positions count separately).

• "abc" -> 3; "aaa" -> 6 (a, a, a, aa, aa, aaa).
• Constraints: 1 <= |s| <= 1000, lowercase.

How the interviewer asks / follow-ups.

• Disguise: "Count the number of symmetric sub-sequences of events in a log for anomaly scoring."
• Follow-ups: O(n) with Manacher? Return the substrings, not only the count? Count distinct palindromic substrings (needs a palindromic tree/hashing)? Large n (n = 10^5 requires Manacher)?
• Evaluating: same center-expansion idea as problem 8, but counting each successful expansion.

Approach 1: Brute force. Check each of the O(n^2) substrings for palindromicity in O(n). Time O(n^3), space O(1).

Approach 2: DP. dp[i][j] as before; count the trues. Time O(n^2), space O(n^2).

Approach 3: Expand around centers (optimal practical). Intuition: every successful step of an expansion is one new palindrome. For each of the 2n-1 centers, count how many expansions succeed. Trace "aaa": center 0 odd: a (1); even (0,1): aa (1), then l=-1 stop. Center 1 odd: a, aaa (2); even (1,2): aa (1). Center 2 odd: a (1); even (2,3) out of range (0). Total 1+1+2+1+1 = 6.

Java code.

static int countSubstrings(String s) {
    int count = 0;
    for (int c = 0; c < s.length(); c++) {
        count += countAround(s, c, c);       // odd-length palindromes centered at c
        count += countAround(s, c, c + 1);   // even-length palindromes between c and c+1
    }
    return count;
}

private static int countAround(String s, int l, int r) {
    int n = 0;
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        n++;            // each successful expansion is a distinct palindrome
        l--; r++;
    }
    return n;
}

Complexity.

• Brute: Time O(n^3), Space O(1).
• DP: Time O(n^2), Space O(n^2).
• Expand around center: Time O(n^2) worst case ("aaaa" has Θ(n^2) palindromes), Space O(1).
• Manacher: Time O(n), Space O(n) (sum of radii).

Edge cases / pitfalls.

• Single characters each count (answer >= n).
• Count fits in int for n <= 1000 (max ~ n(n+1)/2); for 10^5 use long.
• Do not forget the even centers.

Pattern & related problems. Expand from center. Related: Longest Palindromic Substring (5), Palindrome Partitioning (131), Longest Palindromic Subsequence (516), Count Different Palindromic Subsequences (730).

10. Encode and Decode Strings (Medium · LeetCode #271 · Premium)

Problem statement. Design encode(List<String>) -> String and decode(String) -> List<String> such that decode(encode(strs)) equals strs. Strings can contain any characters, including your delimiter, and may be empty.

• ["Hello","World"] -> some string -> back to ["Hello","World"]; [""] must round-trip; [] must round-trip.
• Constraints: 0 <= strs.length <= 200, 0 <= len <= 200, any of the 256 ASCII chars. Must be stateless (no static/global state).

How the interviewer asks / follow-ups.

• Disguise: "Serialize a batch of free-text fields (narration, merchant name) into one message payload / one Kafka record and parse it back safely" - essentially designing a wire format.
• Follow-ups: why not a simple delimiter like , (collision)? Escaping approach vs length-prefix; binary-safe framing (fixed 4-byte length header, as ISO 8583 / TLV do); Unicode (character count vs byte count - define lengths in bytes of UTF-8 for network protocols); streaming decode; versioning and checksum; max length limits and malicious inputs (validate lengths before allocation).
• Evaluating: protocol design thinking, robustness over cleverness, handling empty strings and delimiter characters in data.

Approach 1: Naive delimiter. Join with a special char (e.g. "\u0000" or ","). Breaks if the data contains the delimiter. Unsafe.

Approach 2: Escape-based delimiter. Pick delimiter / and escape occurrences in data (/ -> //, separator /:). Correct but fiddly; decoding needs a state machine. Time O(total length), space O(total).

Approach 3: Length-prefix framing (optimal / standard). Intuition: write <length>#<payload> per string. The decoder reads digits up to #, then takes exactly length characters as payload without interpreting them - so payload can contain #, digits, anything. Trace ["a#b","3#x"] -> "3#a#b3#3#x". Decode: at 0 read 3 then #; take 3 chars a#b; next at index 5: read 3, #, take 3#x. Empty string encodes as 0#.

Java code.

public class Codec {
    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String s : strs) sb.append(s.length()).append('#').append(s); // len#payload
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String data) {
        List<String> res = new ArrayList<>();
        int i = 0;
        while (i < data.length()) {
            int hash = data.indexOf('#', i);                       // first '#' after i is the length terminator
            int len = Integer.parseInt(data.substring(i, hash));
            res.add(data.substring(hash + 1, hash + 1 + len));     // take exactly len chars, no interpretation
            i = hash + 1 + len;
        }
        return res;
    }
}

Note: String.length() counts UTF-16 units and substring uses the same units, so round-tripping is consistent in Java. For a cross-language wire format, prefix with the UTF-8 byte length instead.

Complexity.

• Naive delimiter: Time O(L), Space O(L) but incorrect for delimiter-containing data.
• Escaping: Time O(L), Space O(L), where L is total characters.
• Length-prefix: Time O(L) - encode and decode each touch every char once (indexOf only scans digits since the first # follows the length); Space O(L) for output.

Edge cases / pitfalls.

• Empty list ("" encodes/decodes to []) versus list with one empty string ("0#" -> [""]) - they are distinct.
• Payloads containing #, digits, or 0#-like text (safe because we never parse inside the payload).
• Do not use static fields to carry state between encode and decode.
• Validate input in production (missing #, negative or oversized length) to avoid exceptions or memory attacks.

Pattern & related problems. Length-prefix (TLV) framing / serialization design. Related: Serialize and Deserialize Binary Tree (297), Design HashMap (706), Count and Say (38), String Compression (443).