String Manipulation: Practice Problems with Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

String Manipulation: Complete Guide with Examples

Welcome to the practice problems for string manipulation. If you need a refresher on the code, the code templates have the patterns in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

The problems are ordered by difficulty, but the progression matters as much as the individual solutions.

Longest Common Prefix teaches column-by-column comparison with no extra state. Master this before adding any data structures.
First Unique Character in a String adds frequency counting in two passes. This is the building block behind every anagram and grouping problem.
Longest Palindromic Substring introduces expansion from centers. This is the core string technique and the one you will reach for most.
Palindromic Substrings applies the same expansion technique but counts instead of tracking the longest. If you understood problem 3, this one is a small step.
Reverse Words in a String chains reversals and whitespace handling. It connects directly to the reversal template from the array manipulation pattern.
Longest Duplicate Substring combines rolling hash with binary search. This is where hashing stops being optional and becomes the point.
Shortest Palindrome uses the KMP prefix function to find the longest palindromic prefix. It is the hardest problem in the set and combines matching with construction.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Longest Common Prefix

LeetCode 14 | Difficulty: Easy

Brief: Find the longest string that is a prefix of every string in a list.

Why this pattern: The prefix is found by comparing characters column by column across all strings. No sorting, no hashing, no extra space beyond the answer itself.

Key Insight: Compare the first string against every other string character by character. As soon as a column mismatches or a shorter string ends, everything before that column is the answer.

Visual:

    graph TD
    S["flower, flow, flight"] --> C0{"Column 0: all 'f'?"}
    C0 -->|"Yes"| C1{"Column 1: all 'l'?"}
    C1 -->|"Yes"| C2{"Column 2: all 'o'?"}
    C2 -->|"flight has 'i'"| R["Prefix: fl"]

Code:

var longestCommonPrefix = function(strs) {
    if (strs.length === 0) return "";
    // Compare column by column against the first string.
    // The prefix can never be longer than strs[0], so the
    // first string also bounds the scan.
    for (let i = 0; i < strs[0].length; i++) {
        const c = strs[0][i];
        for (let j = 1; j < strs.length; j++) {
            if (i >= strs[j].length || strs[j][i] !== c) {
                return strs[0].slice(0, i);
            }
        }
    }
    return strs[0];
};

def longest_common_prefix(strs: list[str]) -> str:
    if not strs:
        return ""
    # Compare column by column against the first string.
    # The prefix can never be longer than strs[0], so the
    # first string also bounds the scan.
    for i in range(len(strs[0])):
        c = strs[0][i]
        for s in strs[1:]:
            if i >= len(s) or s[i] != c:
                return strs[0][:i]
    return strs[0]

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        // Compare column by column against the first string.
        // The prefix can never be longer than strs[0], so the
        // first string also bounds the scan.
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        // Compare column by column against the first string.
        // The prefix can never be longer than strs[0], so the
        // first string also bounds the scan.
        for (int i = 0; i < strs[0].size(); i++) {
            char c = strs[0][i];
            for (int j = 1; j < strs.size(); j++) {
                if (i >= strs[j].size() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    // Compare column by column against the first string.
    // The prefix can never be longer than strs[0], so the
    // first string also bounds the scan.
    for i := 0; i < len(strs[0]); i++ {
        c := strs[0][i]
        for j := 1; j < len(strs); j++ {
            if i >= len(strs[j]) || strs[j][i] != c {
                return strs[0][:i]
            }
        }
    }
    return strs[0]
}

def longest_common_prefix(strs)
  return "" if strs.empty?
  # Compare column by column against the first string.
  # The prefix can never be longer than strs[0], so the
  # first string also bounds the scan.
  (0...strs[0].length).each do |i|
    c = strs[0][i]
    strs.drop(1).each do |s|
      return strs[0][0...i] if i >= s.length || s[i] != c
    end
  end
  strs[0]
end

The solution bounds the scan by the first string because the common prefix cannot be longer than any single input. The inner loop returns as soon as one column fails, so the common case stops early instead of scanning everything.

2. First Unique Character in a String

LeetCode 387 | Difficulty: Easy

Brief: Return the index of the first character that appears exactly once in a string, or -1 if none does.

Why this pattern: Frequency counting in two passes. The first pass builds the counts, the second pass finds the first character with a count of one.

Key Insight: The order matters. Count every character first, then scan the string in its original order so the answer is the earliest index, not the earliest character alphabetically.

Visual:

    graph TD
    A["s: leetcode"] --> B["Pass 1: count each character"]
    B --> C["l:1 e:3 t:1 c:1 o:1 d:1"]
    C --> D["Pass 2: first character with count 1"]
    D --> E["l at index 0"]

Code:

var firstUniqChar = function(s) {
    const count = {};
    // First pass records how many times each character
    // appears. Second pass finds the first character
    // that appears exactly once.
    for (const c of s) count[c] = (count[c] || 0) + 1;
    for (let i = 0; i < s.length; i++) {
        if (count[s[i]] === 1) return i;
    }
    return -1;
};

def first_uniq_char(s: str) -> int:
    count = {}
    # First pass records how many times each character
    # appears. Second pass finds the first character
    # that appears exactly once.
    for c in s:
        count[c] = count.get(c, 0) + 1
    for i, c in enumerate(s):
        if count[c] == 1:
            return i
    return -1

class Solution {
    public int firstUniqChar(String s) {
        int[] count = new int[26];
        // First pass records how many times each character
        // appears. Second pass finds the first character
        // that appears exactly once.
        for (char c : s.toCharArray()) count[c - 'a']++;
        for (int i = 0; i < s.length(); i++) {
            if (count[s.charAt(i) - 'a'] == 1) return i;
        }
        return -1;
    }
}

class Solution {
public:
    int firstUniqChar(string s) {
        int count[26] = {0};
        // First pass records how many times each character
        // appears. Second pass finds the first character
        // that appears exactly once.
        for (char c : s) count[c - 'a']++;
        for (int i = 0; i < s.size(); i++) {
            if (count[s[i] - 'a'] == 1) return i;
        }
        return -1;
    }
};

func firstUniqChar(s string) int {
    count := make([]int, 26)
    // First pass records how many times each character
    // appears. Second pass finds the first character
    // that appears exactly once.
    for i := 0; i < len(s); i++ {
        count[s[i]-'a']++
    }
    for i := 0; i < len(s); i++ {
        if count[s[i]-'a'] == 1 {
            return i
        }
    }
    return -1
}

def first_uniq_char(s)
  count = Hash.new(0)
  # First pass records how many times each character
  # appears. Second pass finds the first character
  # that appears exactly once.
  s.each_char { |c| count[c] += 1 }
  s.each_char.with_index do |c, i|
    return i if count[c] == 1
  end
  -1
end

The two passes are what make the answer correct. A single pass cannot know whether a character is unique until the whole string has been seen, and iterating over the map afterward would lose the original order.

Medium Problems

3. Longest Palindromic Substring

LeetCode 5 | Difficulty: Medium

Brief: Find the longest substring that reads the same forward and backward.

Why this pattern: Checking every substring as a palindrome costs

O(N^3)

. Expanding from each center instead treats every palindrome as a window that grows outward, and each center costs only as much as the longest palindrome around it.

Key Insight: A palindrome has a center. Odd-length palindromes center on one character, even-length ones center between two characters. Try every center, expand while the edges match, and keep the longest result.

Visual:

    graph TD
    A["s: babad"] --> B["Center at index 1 (a)"]
    B --> C["b matches b"]
    C --> D["a vs d mismatch"]
    D --> E["Palindromes: b, aba"]
    E --> F["Longest so far: aba"]

Code:

var longestPalindrome = function(s) {
    const expand = (left, right) => {
        // Grow the window while the two edges still match.
        // A mismatch or a walk off the string ends the expansion.
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    };

    let best = "";
    for (let i = 0; i < s.length; i++) {
        // Odd-length palindromes center on one character,
        // even-length ones center between two characters.
        const odd = expand(i, i);
        const even = expand(i, i + 1);
        if (odd.length > best.length) best = odd;
        if (even.length > best.length) best = even;
    }
    return best;
};

def longest_palindrome(s: str) -> str:
    def expand(left: int, right: int) -> str:
        # Grow the window while the two edges still match.
        # A mismatch or a walk off the string ends the expansion.
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]

    best = ""
    for i in range(len(s)):
        # Odd-length palindromes center on one character,
        # even-length ones center between two characters.
        odd = expand(i, i)
        even = expand(i, i + 1)
        if len(odd) > len(best):
            best = odd
        if len(even) > len(best):
            best = even
    return best

class Solution {
    public String longestPalindrome(String s) {
        String best = "";
        for (int i = 0; i < s.length(); i++) {
            // Odd-length palindromes center on one character,
            // even-length ones center between two characters.
            String odd = expand(s, i, i);
            String even = expand(s, i, i + 1);
            if (odd.length() > best.length()) best = odd;
            if (even.length() > best.length()) best = even;
        }
        return best;
    }

    private String expand(String s, int left, int right) {
        // Grow the window while the two edges still match.
        // A mismatch or a walk off the string ends the expansion.
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }
}

class Solution {
public:
    string longestPalindrome(string s) {
        string best;
        for (int i = 0; i < s.size(); i++) {
            // Odd-length palindromes center on one character,
            // even-length ones center between two characters.
            string odd = expand(s, i, i);
            string even = expand(s, i, i + 1);
            if (odd.size() > best.size()) best = odd;
            if (even.size() > best.size()) best = even;
        }
        return best;
    }

    string expand(string& s, int left, int right) {
        // Grow the window while the two edges still match.
        // A mismatch or a walk off the string ends the expansion.
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return s.substr(left + 1, right - left - 1);
    }
};

func longestPalindrome(s string) string {
    best := ""
    expand := func(left, right int) string {
        // Grow the window while the two edges still match.
        // A mismatch or a walk off the string ends the expansion.
        for left >= 0 && right < len(s) && s[left] == s[right] {
            left--
            right++
        }
        return s[left+1 : right]
    }

    for i := 0; i < len(s); i++ {
        // Odd-length palindromes center on one character,
        // even-length ones center between two characters.
        if odd := expand(i, i); len(odd) > len(best) {
            best = odd
        }
        if even := expand(i, i+1); len(even) > len(best) {
            best = even
        }
    }
    return best
}

def longest_palindrome(s)
  best = ""
  expand = lambda do |left, right|
    # Grow the window while the two edges still match.
    # A mismatch or a walk off the string ends the expansion.
    while left >= 0 && right < s.length && s[left] == s[right]
      left -= 1
      right += 1
    end
    s[(left + 1)...right]
  end

  (0...s.length).each do |i|
    # Odd-length palindromes center on one character,
    # even-length ones center between two characters.
    odd = expand.call(i, i)
    even = expand.call(i, i + 1)
    best = odd if odd.length > best.length
    best = even if even.length > best.length
  end
  best
end

The expansion stops one step past the mismatch, so the returned slice starts at left + 1 and ends before right. Both center types are required: skipping the even case misses every even-length palindrome, which is the classic bug in this solution.

4. Palindromic Substrings

LeetCode 647 | Difficulty: Medium

Brief: Count how many substrings of a string are palindromes.

Why this pattern: The same expansion-from-center mechanics as the previous problem, but each matched pair counts one palindrome instead of tracking the longest window.

Key Insight: Every expansion step that matches produces exactly one new palindrome. Each center yields one palindrome per successful expansion, so counting matches is counting palindromes.

Visual:

    graph TD
    A["s: aaa"] --> B["Center (0,0): a"]
    B --> C["Center (0,1): aa"]
    C --> D["Center (1,1): a, aaa"]
    D --> E["Total: 6 palindromes"]

Code:

var countSubstrings = function(s) {
    let count = 0;
    // Every center produces one palindrome per matched pair.
    // Odd centers are single characters, even centers sit
    // between two characters.
    for (let i = 0; i < s.length; i++) {
        let left = i, right = i;
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            count++;
            left--;
            right++;
        }
        left = i;
        right = i + 1;
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            count++;
            left--;
            right++;
        }
    }
    return count;
};

def count_substrings(s: str) -> int:
    count = 0
    # Every center produces one palindrome per matched pair.
    # Odd centers are single characters, even centers sit
    # between two characters.
    for i in range(len(s)):
        left = right = i
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        left, right = i, i + 1
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    return count

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        // Every center produces one palindrome per matched pair.
        // Odd centers are single characters, even centers sit
        // between two characters.
        for (int i = 0; i < s.length(); i++) {
            int left = i, right = i;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                count++;
                left--;
                right++;
            }
            left = i;
            right = i + 1;
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                count++;
                left--;
                right++;
            }
        }
        return count;
    }
}

class Solution {
public:
    int countSubstrings(string s) {
        int count = 0;
        // Every center produces one palindrome per matched pair.
        // Odd centers are single characters, even centers sit
        // between two characters.
        for (int i = 0; i < s.size(); i++) {
            int left = i, right = i;
            while (left >= 0 && right < s.size() && s[left] == s[right]) {
                count++;
                left--;
                right++;
            }
            left = i;
            right = i + 1;
            while (left >= 0 && right < s.size() && s[left] == s[right]) {
                count++;
                left--;
                right++;
            }
        }
        return count;
    }
};

func countSubstrings(s string) int {
    count := 0
    // Every center produces one palindrome per matched pair.
    // Odd centers are single characters, even centers sit
    // between two characters.
    for i := 0; i < len(s); i++ {
        left, right := i, i
        for left >= 0 && right < len(s) && s[left] == s[right] {
            count++
            left--
            right++
        }
        left, right = i, i+1
        for left >= 0 && right < len(s) && s[left] == s[right] {
            count++
            left--
            right++
        }
    }
    return count
}

def count_substrings(s)
  count = 0
  # Every center produces one palindrome per matched pair.
  # Odd centers are single characters, even centers sit
  # between two characters.
  (0...s.length).each do |i|
    left = right = i
    while left >= 0 && right < s.length && s[left] == s[right]
      count += 1
      left -= 1
      right += 1
    end
    left = i
    right = i + 1
    while left >= 0 && right < s.length && s[left] == s[right]
      count += 1
      left -= 1
      right += 1
    end
  end
  count
end

The counting works because each successful expansion adds exactly one palindrome: the window between the current edges. The two expansion loops never double count, because an odd and an even center cannot produce the same substring.

5. Reverse Words in a String

LeetCode 151 | Difficulty: Medium

Brief: Reverse the order of the words in a sentence, keeping single spaces between words and removing leading, trailing, and repeated spaces.

Why this pattern: Word reversal chains string primitives: splitting on whitespace, reversing the word order, and joining back with single spaces. The in-place alternative reverses the whole string and then reverses each word, which is the three-reversal idea from the array manipulation pattern applied to text.

Key Insight: The whitespace rules do the work. Splitting on runs of whitespace handles leading, trailing, and repeated spaces in one step, and joining with a single space normalizes the result.

Visual:

    graph LR
    A["the sky is blue"] --> B["Split into words"]
    B --> C["the, sky, is, blue"]
    C --> D["Reverse the order"]
    D --> E["blue, is, sky, the"]
    E --> F["blue is sky the"]

Code:

var reverseWords = function(s) {
    // Splitting on runs of whitespace handles leading,
    // trailing, and repeated spaces in one step.
    const words = s.trim().split(/\s+/);
    return words.reverse().join(" ");
};

class Solution {
    public String reverseWords(String s) {
        // Split on runs of whitespace, then reverse the
        // word order and join with single spaces.
        String[] words = s.trim().split("\\s+");
        StringBuilder result = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            result.append(words[i]);
            if (i > 0) result.append(" ");
        }
        return result.toString();
    }
}

class Solution {
public:
    string reverseWords(string s) {
        // istringstream already skips runs of whitespace,
        // so repeated spaces never produce empty words.
        istringstream in(s);
        string word;
        vector<string> words;
        while (in >> word) words.push_back(word);

        string result;
        for (int i = words.size() - 1; i >= 0; i--) {
            result += words[i];
            if (i > 0) result += " ";
        }
        return result;
    }
};

func reverseWords(s string) string {
    // strings.Fields splits on any run of whitespace and
    // drops empty tokens, so repeated spaces are handled.
    words := strings.Fields(s)
    for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
        words[i], words[j] = words[j], words[i]
    }
    return strings.Join(words, " ")
}

The word-based solution is the shortest correct answer, but interviewers often ask for the in-place version that uses

O(1)

extra space. That version reverses the whole character array, then reverses each word back into order. It is the same three-reversal idea covered in Array Manipulation , applied to words instead of array segments.

Hard Problems

6. Longest Duplicate Substring

LeetCode 1044 | Difficulty: Hard

Brief: Find the longest substring that appears at least twice in a string.

Why this pattern: Duplicate detection of a fixed length is a rolling hash problem. Rabin-Karp-style hashing checks whether any window of length L repeats in

O(N)

time, and binary search finds the largest L that works.

Key Insight: The answer length is monotonic. If a duplicate substring of length 5 exists, a duplicate of length 4 also exists, because the shorter one is a substring of the longer one. That monotonicity makes binary search valid, and rolling hashes make each length check linear.

Visual:

    graph TD
    A["Binary search on length L"] --> B["Rolling hash: any window of length L repeated?"]
    B -->|"Duplicate found"| C["Try a longer length"]
    B -->|"No duplicate"| D["Try a shorter length"]
    C --> B
    D --> B

Code:

var longestDupSubstring = function(s) {
    let n = s.length;
    let base = 26n, mod = 2n**63n - 1n;
    let left = 1, right = n - 1;
    let res = "";

    // Binary search on the duplicate length. Any length that
    // works is a signal to try longer ones.
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let found = check(mid);
        if (found !== null) {
            res = s.substring(found, found + mid);
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    function check(len) {
        let h = 0n;
        for (let i = 0; i < len; i++) h = (h * base + BigInt(s.charCodeAt(i) - 97)) % mod;
        let seen = new Set([h]);
        let aL = 1n;
        for (let i = 0; i < len; i++) aL = (aL * base) % mod;

        // Slide the window, reusing the previous hash.
        // The dropped leftmost character and the added
        // rightmost one update the hash in constant time.
        for (let i = 1; i <= n - len; i++) {
            h = (h * base - BigInt(s.charCodeAt(i - 1) - 97) * aL % mod + mod) % mod;
            h = (h + BigInt(s.charCodeAt(i + len - 1) - 97)) % mod;
            if (seen.has(h)) return i;
            seen.add(h);
        }
        return null;
    }
    return res;
};

def longestDupSubstring(s: str) -> str:
    n = len(s)
    nums = [ord(c) - ord('a') for c in s]
    base = 26
    mod = 2**63 - 1

    def check(length):
        h = 0
        for i in range(length):
            h = (h * base + nums[i]) % mod
        seen = {h}
        aL = pow(base, length, mod)
        # Slide the window, reusing the previous hash.
        # The dropped leftmost character and the added
        # rightmost one update the hash in constant time.
        for i in range(1, n - length + 1):
            h = (h * base - nums[i - 1] * aL % mod + mod) % mod
            h = (h + nums[i + length - 1]) % mod
            if h in seen:
                return i
            seen.add(h)
        return -1

    left, right = 1, n - 1
    start, max_len = 0, 0
    while left <= right:
        mid = (left + right) // 2
        pos = check(mid)
        if pos != -1:
            start, max_len = pos, mid
            left = mid + 1
        else:
            right = mid - 1
    return s[start:start + max_len]

class Solution {
    public String longestDupSubstring(String s) {
        int n = s.length();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = s.charAt(i) - 'a';
        long mod = (1L << 61) - 1;
        int left = 1, right = n - 1;
        int start = 0, maxLen = 0;
        // Binary search on the duplicate length. Any length
        // that works is a signal to try longer ones.
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int pos = check(mid, n, nums, mod);
            if (pos != -1) {
                start = pos;
                maxLen = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return s.substring(start, start + maxLen);
    }

    private int check(int len, int n, int[] nums, long mod) {
        long h = 0, aL = 1, base = 26;
        for (int i = 0; i < len; i++) {
            h = (h * base + nums[i]) % mod;
            aL = (aL * base) % mod;
        }
        Set<Long> seen = new HashSet<>();
        seen.add(h);
        // Slide the window, reusing the previous hash.
        // The dropped leftmost character and the added
        // rightmost one update the hash in constant time.
        for (int i = 1; i <= n - len; i++) {
            h = (h * base - nums[i - 1] * aL % mod + mod) % mod;
            h = (h + nums[i + len - 1]) % mod;
            if (seen.contains(h)) return i;
            seen.add(h);
        }
        return -1;
    }
}

class Solution {
public:
    string longestDupSubstring(string s) {
        int n = s.size();
        vector<int> nums(n);
        for (int i = 0; i < n; i++) nums[i] = s[i] - 'a';
        long long mod = (1ULL << 61) - 1;
        int left = 1, right = n - 1, start = 0, maxLen = 0;
        // Binary search on the duplicate length. Any length
        // that works is a signal to try longer ones.
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int pos = check(mid, n, nums, mod);
            if (pos != -1) {
                start = pos;
                maxLen = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return s.substr(start, maxLen);
    }

    int check(int len, int n, vector<int>& nums, long long mod) {
        __int128 h = 0, aL = 1, base = 26;
        for (int i = 0; i < len; i++) {
            h = (h * base + nums[i]) % mod;
            aL = (aL * base) % mod;
        }
        unordered_set<long long> seen;
        seen.insert((long long)h);
        // Slide the window, reusing the previous hash.
        // The dropped leftmost character and the added
        // rightmost one update the hash in constant time.
        for (int i = 1; i <= n - len; i++) {
            h = (h * base - nums[i - 1] * aL % mod + mod) % mod;
            h = (h + nums[i + len - 1]) % mod;
            if (seen.count((long long)h)) return i;
            seen.insert((long long)h);
        }
        return -1;
    }
};

func longestDupSubstring(s string) string {
    n := len(s)
    nums := make([]int, n)
    for i := 0; i < n; i++ {
        nums[i] = int(s[i] - 'a')
    }
    mod := uint64(1<<61 - 1)
    left, right := 1, n-1
    resStart, resLen := 0, 0
    // Binary search on the duplicate length. Any length
    // that works is a signal to try longer ones.
    for left <= right {
        mid := (left + right) / 2
        pos := check(mid, n, nums, mod)
        if pos != -1 {
            resStart, resLen = pos, mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return s[resStart : resStart+resLen]
}

func check(length, n int, nums []int, mod uint64) int {
    var h, aL, base uint64 = 0, 1, 26
    for i := 0; i < length; i++ {
        h = (h*base + uint64(nums[i])) % mod
        aL = (aL * base) % mod
    }
    seen := map[uint64]struct{}{h: {}}
    // Slide the window, reusing the previous hash.
    // The dropped leftmost character and the added
    // rightmost one update the hash in constant time.
    for i := 1; i <= n-length; i++ {
        h = (h*base + uint64(nums[i+length-1])) % mod
        h = (h - (uint64(nums[i-1])*aL)%mod + mod) % mod
        if _, ok := seen[h]; ok {
            return i
        }
        seen[h] = struct{}{}
    }
    return -1
}

def longest_dup_substring(s)
  n = s.length
  nums = s.chars.map { |c| c.ord - 'a'.ord }
  base = 26
  mod = (1 << 61) - 1

  check = lambda do |length|
    h = 0
    al = 1
    length.times do |i|
      h = (h * base + nums[i]) % mod
      al = (al * base) % mod
    end
    seen = { h => true }
    # Slide the window, reusing the previous hash.
    # The dropped leftmost character and the added
    # rightmost one update the hash in constant time.
    (1..n - length).each do |i|
      h = (h * base - nums[i - 1] * al % mod + mod) % mod
      h = (h + nums[i + length - 1]) % mod
      return i if seen[h]
      seen[h] = true
    end
    nil
  end

  left, right = 1, n - 1
  res_start, res_len = 0, 0
  while left <= right
    mid = (left + right) / 2
    pos = check.call(mid)
    if pos
      res_start, res_len = pos, mid
      left = mid + 1
    else
      right = mid - 1
    end
  end
  s[res_start, res_len]
end

The rolling hash update is where the speed comes from. Each window hash is derived from the previous one in constant time, so each length check costs

O(N)

. The binary search adds a

O(log N)

factor, giving

O(N log N)

overall. Hash collisions are possible in principle, so the C++ version uses wider intermediate arithmetic to keep the risk negligible.

7. Shortest Palindrome

LeetCode 214 | Difficulty: Hard

Brief: Prepend the fewest characters possible to a string so the result is a palindrome.

Why this pattern: The answer mirrors the part of the string that is not already a palindromic prefix. Finding the longest palindromic prefix is exactly what the KMP prefix function does when the string is joined with its reverse.

Key Insight: Build s + "#" + reverse(s) and compute the prefix function. The final table value is the length of the longest palindromic prefix, because it is the longest prefix of the combined string that matches its own suffix. Everything after that prefix must be mirrored in front.

Visual:

    graph LR
    A["s: aacecaaa"] --> B["combined: aacecaaa#aaacecaa"]
    B --> C["Prefix function: longest prefix that is also a suffix"]
    C --> D["aacecaa, length 7"]
    D --> E["Remainder a is mirrored in front"]
    E --> F["aaacecaaa"]

Code:

var shortestPalindrome = function(s) {
    // The prefix function over s + "#" + reverse(s) finds
    // the longest palindromic prefix in the final table value.
    const combined = s + "#" + s.split("").reverse().join("");
    const pi = new Array(combined.length).fill(0);
    for (let i = 1; i < combined.length; i++) {
        let j = pi[i - 1];
        while (j > 0 && combined[i] !== combined[j]) j = pi[j - 1];
        if (combined[i] === combined[j]) j++;
        pi[i] = j;
    }
    // The characters after the palindromic prefix must be
    // prepended in reverse to make the whole string a palindrome.
    const k = pi[combined.length - 1];
    return s.slice(k).split("").reverse().join("") + s;
};

def shortest_palindrome(s: str) -> str:
    # The prefix function over s + "#" + reversed(s) finds
    # the longest palindromic prefix in the final table value.
    combined = s + "#" + s[::-1]
    pi = [0] * len(combined)
    for i in range(1, len(combined)):
        j = pi[i - 1]
        while j > 0 and combined[i] != combined[j]:
            j = pi[j - 1]
        if combined[i] == combined[j]:
            j += 1
        pi[i] = j
    # The characters after the palindromic prefix must be
    # prepended in reverse to make the whole string a palindrome.
    k = pi[-1]
    return s[k:][::-1] + s

class Solution {
    public String shortestPalindrome(String s) {
        // The prefix function over s + "#" + reversed(s) finds
        // the longest palindromic prefix in the final table value.
        String combined = s + "#" + new StringBuilder(s).reverse().toString();
        int[] pi = new int[combined.length()];
        for (int i = 1; i < combined.length(); i++) {
            int j = pi[i - 1];
            while (j > 0 && combined.charAt(i) != combined.charAt(j)) j = pi[j - 1];
            if (combined.charAt(i) == combined.charAt(j)) j++;
            pi[i] = j;
        }
        // The characters after the palindromic prefix must be
        // prepended in reverse to make the whole string a palindrome.
        int k = pi[combined.length() - 1];
        return new StringBuilder(s.substring(k)).reverse().toString() + s;
    }
}

class Solution {
public:
    string shortestPalindrome(string s) {
        // The prefix function over s + "#" + reversed(s) finds
        // the longest palindromic prefix in the final table value.
        string rev = s;
        reverse(rev.begin(), rev.end());
        string combined = s + "#" + rev;
        int n = combined.size();
        vector<int> pi(n, 0);
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && combined[i] != combined[j]) j = pi[j - 1];
            if (combined[i] == combined[j]) j++;
            pi[i] = j;
        }
        // The characters after the palindromic prefix must be
        // prepended in reverse to make the whole string a palindrome.
        int k = pi[n - 1];
        string tail = s.substr(k);
        reverse(tail.begin(), tail.end());
        return tail + s;
    }
};

func shortestPalindrome(s string) string {
    // The prefix function over s + "#" + reversed(s) finds
    // the longest palindromic prefix in the final table value.
    combined := s + "#" + reverse(s)
    pi := make([]int, len(combined))
    for i := 1; i < len(combined); i++ {
        j := pi[i-1]
        for j > 0 && combined[i] != combined[j] {
            j = pi[j-1]
        }
        if combined[i] == combined[j] {
            j++
        }
        pi[i] = j
    }
    // The characters after the palindromic prefix must be
    // prepended in reverse to make the whole string a palindrome.
    k := pi[len(combined)-1]
    return reverse(s[k:]) + s
}

func reverse(s string) string {
    bytes := []byte(s)
    for i, j := 0, len(bytes)-1; i < j; i, j = i+1, j-1 {
        bytes[i], bytes[j] = bytes[j], bytes[i]
    }
    return string(bytes)
}

def shortest_palindrome(s)
  # The prefix function over s + "#" + reversed(s) finds
  # the longest palindromic prefix in the final table value.
  combined = s + "#" + s.reverse
  pi = Array.new(combined.length, 0)
  (1...combined.length).each do |i|
    j = pi[i - 1]
    while j > 0 && combined[i] != combined[j]
      j = pi[j - 1]
    end
    j += 1 if combined[i] == combined[j]
    pi[i] = j
  end
  # The characters after the palindromic prefix must be
  # prepended in reverse to make the whole string a palindrome.
  k = pi[-1]
  s[k..-1].reverse + s
end

The separator matters. Without #, the prefix function could match a prefix of s against a suffix of reversed(s) that spans the join point, which would overstate the palindromic prefix length. The # makes the combined string prefix and suffix align only through the true palindromic prefix of s. The total cost is

O(N)

time and

O(N)

space for the prefix table.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These seven problems cover the full range of string manipulation techniques. Start with the column comparison in Longest Common Prefix, build up through frequency counting and center expansion, then finish with the rolling hash and prefix function problems that combine string matching with binary search and KMP. By the end, you should be able to recognize which of the four moves applies to a problem and reach for the right template.

Done with these problems? The app has more, plus a spaced repetition system that brings problems back right before you would forget them. Continue your prep .