Strings

Strings are sequences of characters, one of the most common data types in programming. Mastering string algorithms is essential for coding interviews and real-world applications.

---

Why This Matters in Interviews

String manipulation problems appear frequently in technical interviews because they test:

• Algorithmic thinking: Pattern matching, searching, and optimization
• Edge case handling: Empty strings, special characters, encoding issues
• Time/space complexity: Understanding trade-offs between different approaches
• Problem decomposition: Breaking complex string problems into smaller parts

Interviewers use string problems to assess your ability to work with fundamental data structures and apply algorithmic techniques.

---

Core Concepts

• String immutability: In many languages, strings are immutable (Java, Python, JavaScript)
• Character encoding: ASCII, Unicode, UTF-8 handling
• Substring vs subsequence: Substring is contiguous, subsequence is not
• Pattern matching: Finding occurrences of a pattern in text
• String transformations: Reversing, rotating, permuting strings
• Palindrome detection: Strings that read the same forwards and backwards
• Anagram detection: Strings with same characters in different order

---

Detailed Explanation

String Operations

Basic Operations:

• Length: O(1) in most languages
• Access by index: O(1)
• Concatenation: O(n + m) where n, m are string lengths
• Substring extraction: O(k) where k is substring length
• Search: O(n) for naive, O(n + m) for KMP

Common Operations:

// String creation
const str = "Hello World";

// Length
str.length; // 11

// Access
str[0]; // 'H'
str.charAt(0); // 'H'

// Substring
str.substring(0, 5); // "Hello"
str.slice(0, 5); // "Hello"

// Search
str.indexOf("World"); // 6
str.includes("World"); // true

// Replace
str.replace("World", "Universe"); // "Hello Universe"

// Split
str.split(" "); // ["Hello", "World"]

// Join
["Hello", "World"].join(" "); // "Hello World"

Pattern Matching Algorithms

1. Naive String Search:

function naiveSearch(text: string, pattern: string): number[] {
  const positions: number[] = [];
  const n = text.length;
  const m = pattern.length;
  
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) {
      j++;
    }
    if (j === m) {
      positions.push(i);
    }
  }
  
  return positions;
}

// Time: O(n * m), Space: O(1)

2. KMP (Knuth-Morris-Pratt) Algorithm:

function kmpSearch(text: string, pattern: string): number[] {
  const positions: number[] = [];
  const lps = buildLPS(pattern);
  let i = 0; // text index
  let j = 0; // pattern index
  
  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;
    }
    
    if (j === pattern.length) {
      positions.push(i - j);
      j = lps[j - 1];
    } else if (i < text.length && text[i] !== pattern[j]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
  
  return positions;
}

function buildLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);
  let len = 0;
  let i = 1;
  
  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  
  return lps;
}

// Time: O(n + m), Space: O(m)

3. Rabin-Karp Algorithm:

function rabinKarp(text: string, pattern: string): number[] {
  const positions: number[] = [];
  const n = text.length;
  const m = pattern.length;
  const base = 256;
  const mod = 101; // Prime number
  
  // Calculate hash of pattern and first window
  let patternHash = 0;
  let textHash = 0;
  let h = 1;
  
  // h = base^(m-1) % mod
  for (let i = 0; i < m - 1; i++) {
    h = (h * base) % mod;
  }
  
  // Calculate initial hashes
  for (let i = 0; i < m; i++) {
    patternHash = (base * patternHash + pattern.charCodeAt(i)) % mod;
    textHash = (base * textHash + text.charCodeAt(i)) % mod;
  }
  
  // Slide pattern over text
  for (let i = 0; i <= n - m; i++) {
    if (patternHash === textHash) {
      // Check if strings actually match (hash collision)
      let match = true;
      for (let j = 0; j < m; j++) {
        if (text[i + j] !== pattern[j]) {
          match = false;
          break;
        }
      }
      if (match) {
        positions.push(i);
      }
    }
    
    // Calculate hash for next window
    if (i < n - m) {
      textHash = (base * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % mod;
      if (textHash < 0) {
        textHash += mod;
      }
    }
  }
  
  return positions;
}

// Time: O(n + m) average, O(n * m) worst case, Space: O(1)

Palindrome Detection

function isPalindrome(s: string): boolean {
  // Remove non-alphanumeric and convert to lowercase
  const cleaned = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
  let left = 0;
  let right = cleaned.length - 1;
  
  while (left < right) {
    if (cleaned[left] !== cleaned[right]) {
      return false;
    }
    left++;
    right--;
  }
  
  return true;
}

// Time: O(n), Space: O(1)

Anagram Detection

function isAnagram(s1: string, s2: string): boolean {
  if (s1.length !== s2.length) return false;
  
  const charCount = new Map<string, number>();
  
  // Count characters in s1
  for (const char of s1) {
    charCount.set(char, (charCount.get(char) || 0) + 1);
  }
  
  // Decrement for s2
  for (const char of s2) {
    const count = charCount.get(char);
    if (!count) return false;
    charCount.set(char, count - 1);
  }
  
  // Check all counts are zero
  for (const count of charCount.values()) {
    if (count !== 0) return false;
  }
  
  return true;
}

// Time: O(n), Space: O(1) - limited character set

---

Examples

Longest Palindromic Substring

function longestPalindrome(s: string): string {
  if (s.length < 2) return s;
  
  let start = 0;
  let maxLen = 1;
  
  function expandAroundCenter(left: number, right: number): void {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      const len = right - left + 1;
      if (len > maxLen) {
        maxLen = len;
        start = left;
      }
      left--;
      right++;
    }
  }
  
  for (let i = 0; i < s.length; i++) {
    // Odd length palindromes
    expandAroundCenter(i, i);
    // Even length palindromes
    expandAroundCenter(i, i + 1);
  }
  
  return s.substring(start, start + maxLen);
}

// Time: O(n²), Space: O(1)

String Compression

function compress(chars: string[]): number {
  let write = 0;
  let read = 0;
  
  while (read < chars.length) {
    const char = chars[read];
    let count = 0;
    
    // Count consecutive characters
    while (read < chars.length && chars[read] === char) {
      read++;
      count++;
    }
    
    // Write character
    chars[write++] = char;
    
    // Write count if > 1
    if (count > 1) {
      const countStr = count.toString();
      for (const digit of countStr) {
        chars[write++] = digit;
      }
    }
  }
  
  return write;
}

// Time: O(n), Space: O(1)

Valid Parentheses

function isValid(s: string): boolean {
  const stack: string[] = [];
  const pairs: { [key: string]: string } = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  
  for (const char of s) {
    if (char in pairs) {
      // Closing bracket
      if (stack.length === 0 || stack.pop() !== pairs[char]) {
        return false;
      }
    } else {
      // Opening bracket
      stack.push(char);
    }
  }
  
  return stack.length === 0;
}

// Time: O(n), Space: O(n)

---

Common Pitfalls

• Off-by-one errors: String indices and substring boundaries. Fix: Use inclusive/exclusive consistently
• Immutable strings: Trying to modify strings directly. Fix: Create new strings or use arrays
• Character encoding: Assuming one byte per character. Fix: Handle Unicode properly
• Case sensitivity: Forgetting to normalize case. Fix: Convert to lowercase/uppercase before comparison
• Empty strings: Not handling empty or null strings. Fix: Add null/empty checks
• Whitespace: Ignoring leading/trailing spaces. Fix: Use trim() or handle explicitly

---

Interview Questions

Beginner

Q: Write a function to reverse a string. Can you do it in-place?

A:

// Using built-in methods
function reverseString(s: string): string {
  return s.split('').reverse().join('');
}

// In-place (using array)
function reverseStringInPlace(s: string[]): void {
  let left = 0;
  let right = s.length - 1;
  
  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]];
    left++;
    right--;
  }
}

// Time: O(n), Space: O(1) for in-place

Key points:

• Two-pointer technique
• Swap characters from both ends
• Handle even/odd length strings

---

Intermediate

Q: Implement a function to check if two strings are anagrams. Optimize for both time and space.

A:

// Approach 1: Sorting
function isAnagramSort(s1: string, s2: string): boolean {
  if (s1.length !== s2.length) return false;
  return s1.split('').sort().join('') === s2.split('').sort().join('');
}
// Time: O(n log n), Space: O(n)

// Approach 2: Character counting (optimal)
function isAnagramOptimal(s1: string, s2: string): boolean {
  if (s1.length !== s2.length) return false;
  
  const count = new Array(26).fill(0); // Assuming lowercase letters only
  
  for (let i = 0; i < s1.length; i++) {
    count[s1.charCodeAt(i) - 'a'.charCodeAt(0)]++;
    count[s2.charCodeAt(i) - 'a'.charCodeAt(0)]--;
  }
  
  return count.every(c => c === 0);
}
// Time: O(n), Space: O(1) - fixed size array

// Approach 3: Hash map (handles Unicode)
function isAnagramUnicode(s1: string, s2: string): boolean {
  if (s1.length !== s2.length) return false;
  
  const map = new Map<string, number>();
  
  for (const char of s1) {
    map.set(char, (map.get(char) || 0) + 1);
  }
  
  for (const char of s2) {
    const count = map.get(char);
    if (!count) return false;
    map.set(char, count - 1);
  }
  
  return true;
}
// Time: O(n), Space: O(k) where k is unique characters

---

Senior

Q: Design a system to find all occurrences of multiple patterns in a large text corpus. The patterns can be added dynamically, and queries should be fast.

A:

class MultiPatternMatcher {
  private trie: TrieNode;
  
  constructor() {
    this.trie = new TrieNode();
  }
  
  // Add pattern to search for
  addPattern(pattern: string): void {
    let node = this.trie;
    for (const char of pattern) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
    node.pattern = pattern;
  }
  
  // Find all patterns in text
  search(text: string): Map<string, number[]> {
    const results = new Map<string, number[]>();
    
    for (let i = 0; i < text.length; i++) {
      let node = this.trie;
      let j = i;
      
      while (j < text.length && node.children.has(text[j])) {
        node = node.children.get(text[j])!;
        
        if (node.isEnd && node.pattern) {
          if (!results.has(node.pattern)) {
            results.set(node.pattern, []);
          }
          results.get(node.pattern)!.push(i);
        }
        
        j++;
      }
    }
    
    return results;
  }
}

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: boolean = false;
  pattern?: string;
}

// Usage
const matcher = new MultiPatternMatcher();
matcher.addPattern("abc");
matcher.addPattern("def");
matcher.addPattern("abcde");

const results = matcher.search("abcdefabc");
// Results: { "abc": [0, 6], "def": [3], "abcde": [0] }

// Alternative: Aho-Corasick algorithm for better performance
// Builds failure links for O(n + m + z) where z is number of matches

Optimizations:

• Trie structure: Efficient pattern storage
• Aho-Corasick: Builds failure links for linear time matching
• Caching: Cache search results for repeated queries
• Parallel processing: Distribute text across multiple workers

---

Key Takeaways

• String immutability: Understand how your language handles strings
• Pattern matching: KMP for single pattern, Aho-Corasick for multiple patterns
• Two-pointer technique: Efficient for palindrome, anagram problems
• Character counting: Use arrays for limited character sets, maps for Unicode
• Time complexity: Naive O(n*m), KMP O(n+m), Rabin-Karp O(n+m) average
• Space optimization: Consider in-place operations when possible
• Edge cases: Empty strings, single characters, special characters, encoding