Strings

Question 1

What is the time complexity of checking if a string is a palindrome?

Answer 1

O(n).

Question 2

What is the KMP algorithm used for?
(likely not needed for META)

Answer 2

Efficient substring search using a partial match table, reducing backtracking to O(n + m).

KMP finds a pattern in a given text in O(n+m) time

KMP has two main steps

1. preprocess the pattern and build the longest prefix suffix array (LPS)
2. Search for the Pattern using LPS

Let’s say we want to search for “ABABCABAB” in a text.

First, we construct the LPS table for “ABABCABAB”:

Pattern Index Pattern LPS Value
0 A 0
1 AB 0
2 ABA 1
3 ABAB 2
4 ABABC 0
5 ABABCA 1
6 ABABCAB 2
7 ABABCABA 3
8 ABABCABAB 4

f there’s a mismatch at index i, the LPS tells us where to jump in the pattern instead of starting over.

Example: If a mismatch happens at index 6, LPS tells us to restart from index 2, not 0.
~~~
function computeLPS(pattern) {
let lps = new Array(pattern.length).fill(0);
let j = 0; // Length of previous longest prefix suffix

for (let i = 1; i < pattern.length; ) {
    if (pattern[i] === pattern[j]) {
        lps[i] = j + 1;
        i++;
        j++;
    } else {
        if (j !== 0) {
            j = lps[j - 1];  // Move back in the pattern
        } else {
            lps[i] = 0;
            i++;
        }
    }
}
return lps; }

function KMP(text, pattern) {
let lps = computeLPS(pattern);
let i = 0, j = 0; // i → text index, j → pattern index

while (i < text.length) {
    if (text[i] === pattern[j]) {
        i++;
        j++;
    }
    
    if (j === pattern.length) {  // Full match found
        console.log(`Pattern found at index ${i - j}`);
        j = lps[j - 1];  // Move j to the next matchable position
    } else if (i < text.length && text[i] !== pattern[j]) {
        if (j !== 0) {
            j = lps[j - 1];  // Jump using LPS
        } else {
            i++;
        }
    }
} } ~~~

Question 3

What is the Rabin-Karp algorithm? (GOOD TO KNOW FOR META)

Answer 3

The Rabin-Karp algorithm is a string-searching algorithm that uses hashing to find a pattern in a text in O(n) average time. It is particularly useful when searching for multiple patterns.

1️⃣ Compute a hash value for the pattern and the first window of the text
2️⃣ Slide the window over the text, computing the new hash in O(1) using a rolling hash formula
3️⃣ If the hash matches, check the actual substring (to avoid hash collisions)
4️⃣ Repeat until the end of the text

function rabinKarp(text, pattern) {
let base = 256; // Base for character hashing
let prime = 101; // Prime number for modulus
let n = text.length, m = pattern.length;
let textHash = 0, patternHash = 0, h = 1;

// Compute h = base^(m-1) % prime
for (let i = 0; i < m - 1; i++) {
    h = (h * base) % prime;
}
  
// Compute hash of pattern and first window of text
for (let i = 0; i < m; i++) {
    patternHash = (base * patternHash + pattern.charCodeAt(i)) % prime;
    textHash = (base * textHash + text.charCodeAt(i)) % prime;
}
  
// Slide the window across the text
for (let i = 0; i <= n - m; i++) {
    // Check if hash matches
    if (patternHash === textHash) {
        // Verify substring match (to avoid false positives)
        if (text.substring(i, i + m) === pattern) {
            console.log(`Pattern found at index ${i}`);
        }
    }
  
    // Compute next window hash using rolling hash formula
    if (i < n - m) {
        textHash = (base * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;
        if (textHash < 0) textHash += prime;  // Ensure positive hash
    }
} }

// Example Usage
rabinKarp(“ABABDABACDABABCABAB”, “ABABCABAB”);

Question 4

What is the Boyer-Moore algorithm used for? (LIKELY NOT NEEDED FOR META)

Answer 4

Skips unnecessary character comparisons by preprocessing the pattern for efficient mismatched character jumps.

Question 5

What is the longest palindromic substring problem, and how is it solved efficiently?

Answer 5

Solved with dynamic programming or Manacher’s algorithm.

Question 6

How can a Trie be used for efficient string matching?

Answer 6

Stores words for efficient prefix searches, reducing lookup time to O(m) for a word of length m.