String Algorithms

Strings are interview favorites

Now that we have covered Arrays and Strings, Hashing, Dynamic Programming, and Advanced Data Structures, we are ready to treat strings as more than just character arrays.

String algorithm problems show up often in MAANG-style interviews because they test several skills at once:

• scanning with clean indexes
• avoiding repeated work
• using hashes safely
• recognizing prefixes, suffixes, and repeated structure
• explaining time complexity under pressure

In this lesson, we will focus on practical tools for substring search and repeated-pattern reasoning: naive matching, KMP, and rolling hash.

Start by identifying the shape

Most interview string problems are not about memorizing one magic algorithm. They are about recognizing the shape of the task.

Common shapes:

Problem asks for... Likely tool Does pattern occur in text? Naive scan, KMP, Rabin-Karp Longest repeated prefix/suffix behavior KMP prefix table Count character frequencies HashMap or array counts from Hashing Longest valid substring under a rule Sliding window from Arrays and Strings Edit distance or subsequences DP from Dynamic Programming

A strong interview answer starts with: What work am I repeating, and can I remember enough to skip it?

The baseline: try every start

Before optimizing, always know the simple version.

For each possible starting index in the text, compare the pattern character by character.

Example:

text:    b a n a n a s
pattern:   a n a
match at index 1
pattern:       a n a
match at index 3

This is easy to code and often acceptable when inputs are small.

Time complexity:

• Let n = text.length()
• Let m = pattern.length()
• Worst case: O(n * m)

The next algorithms improve this by avoiding repeated comparisons.

```java
import java.util.*;

public class Main {
    static List<Integer> naiveSearch(String text, String pattern) {
        List<Integer> matches = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();

        if (m == 0) return matches;

        for (int i = 0; i <= n - m; i++) {
            int j = 0;
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }
            if (j == m) {
                matches.add(i);
            }
        }
        return matches;
    }

    public static void main(String[] args) {
        String text = "bananas";
        String pattern = "ana";
        System.out.println(naiveSearch(text, pattern));
    }
}
```

You use naive substring search on a text of length n and a pattern of length m.

In the worst case, what is the time complexity?

KMP skips smartly

KMP stands for Knuth-Morris-Pratt. It solves substring search in O(n + m) time.

The key insight:

When a mismatch happens, do not restart the pattern from zero if part of what you matched is also a useful prefix.

KMP precomputes an lps array for the pattern.

lps[i] means:

the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i]

Proper prefix means it cannot be the entire substring.

Example pattern: ababaca

i:       0 1 2 3 4 5 6
char:    a b a b a c a
lps:     0 0 1 2 3 0 1

If we matched ababa and then fail, we do not throw away all progress. The lps table tells us the next meaningful pattern position.

Two phases

KMP has two clean parts:

1. Build the lps array for the pattern.
2. Scan the text while using lps to avoid unnecessary resets.

The code looks index-heavy at first, but the logic is consistent:

• i moves through the text
• j moves through the pattern
• on match: advance both
• on mismatch with j > 0: move j back using lps[j - 1]
• on mismatch with j == 0: advance text

Notice that i never moves backward.

```java
import java.util.*;

public class Main {
    static int[] buildLps(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0;
        int i = 1;

        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
        return lps;
    }

    static List<Integer> kmpSearch(String text, String pattern) {
        List<Integer> matches = new ArrayList<>();
        if (pattern.length() == 0) return matches;

        int[] lps = buildLps(pattern);
        int i = 0; // text index
        int j = 0; // pattern index

        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;

                if (j == pattern.length()) {
                    matches.add(i - j);
                    j = lps[j - 1];
                }
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
        return matches;
    }

    public static void main(String[] args) {
        String text = "abxabcabcabyabcaby";
        String pattern = "abcaby";
        System.out.println(kmpSearch(text, pattern));
        System.out.println(Arrays.toString(buildLps(pattern)));
    }
}
```

For the pattern ababaca, what is the LPS array?

Enter your answer as comma-separated values with no spaces.

Example format: 0,1,2

Fill in the blank: _____________

Rabin-Karp idea

KMP uses prefix-suffix structure. Rabin-Karp uses hashing.

Instead of comparing every character of every window, compute a hash for:

• the pattern
• each text window of length m

Then slide the window and update the hash quickly.

text:    c o d e d a i l y
window:  c o d e
next:      o d e d

A rolling hash lets us remove the outgoing character and add the incoming character without rebuilding the whole hash from scratch.

Important interview detail:

Hashes can collide, so when hashes match, verify the actual substring characters.

Typical use cases:

• many substring lookups
• detecting repeated substrings
• plagiarism or document matching style problems
• problems where hashing is easier to reason about than prefix tables

True or false:

If two substrings have the same Rabin-Karp hash, they are guaranteed to be identical.

Choosing the right string tool

Use this practical decision guide:

Situation Good first choice Small input, simple matching Naive search Need guaranteed linear substring search KMP Repeated substring detection or many window hashes Rabin-Karp Character counts, anagrams, uniqueness HashMap or fixed-size array Longest substring with constraints Sliding window Subsequences or edit distance Dynamic Programming

Java interview notes

• String.charAt(i) is usually enough for standard LeetCode-style lowercase/ASCII problems.
• If the prompt mentions Unicode, emojis, or human languages, clarify assumptions.
• Avoid repeated string concatenation in loops; use StringBuilder when building output.
• Always state your complexity in terms of n and m.

Next up, we will move from characters to individual binary digits in Bit Manipulation.