Strings: Patterns, Complexity & Interview Use Cases

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:

1// String creation
2const str = "Hello World";
3
4// Length
5str.length; // 11
6
7// Access
8str[0]; // 'H'
9str.charAt(0); // 'H'
10
11// Substring
12str.substring(0, 5); // "Hello"
13str.slice(0, 5); // "Hello"
14
15// Search
16str.indexOf("World"); // 6
17str.includes("World"

Pattern Matching Algorithms

1. Naive String Search:

1function naiveSearch(text: string, pattern: string): number[] {
2  const positions: number[] = [];
3  const n = text.length;
4  const m = pattern.length;
5  
6  for (let i = 0; i <= n - m; i++) {
7    let j = 0;
8    while (j < m && text[i + j] === pattern[j]) {

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

1function kmpSearch(text: string, pattern: string): number[] {
2  const positions: number[] = [];
3  const lps = buildLPS(pattern);
4  let i = 0; // text index
5  let j = 0; // pattern index
6  
7  while (i < text.length) {
8    if (text[i] === pattern[j]) {
9      i++;
10      j++

3. Rabin-Karp Algorithm:

1function rabinKarp(text: string, pattern: string): number[] {
2  const positions: number[] = [];
3  const n = text.length;
4  const m = pattern.length;
5  const base = 256;
6  const mod = 101; // Prime number
7  
8  // Calculate hash of pattern and first window
9  let patternHash = 0;
10  let textHash = 0;
11  let h = 1;
12  
13  // h = base^(m-1) % mod

Palindrome Detection

1function isPalindrome(s: string): boolean {
2  // Remove non-alphanumeric and convert to lowercase
3  const cleaned = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
4  let left = 0;
5  let right = cleaned.length - 1;
6  
7  while (left < right) {
8    if (cleaned[left]  cleanedright

Anagram Detection

1function isAnagram(s1: string, s2: string): boolean {
2  if (s1.length !== s2.length) return false;
3  
4  const charCount = new Map<string, number>();
5  
6  // Count characters in s1
7  for (const char of s1) {
8    charCount.set(char, (charCount.get(char) || 0) + 1);
9  }

Examples

Longest Palindromic Substring

1function longestPalindrome(s: string): string {
2  if (s.length < 2) return s;
3  
4  let start = 0;
5  let maxLen = 1;
6  
7  function expandAroundCenter(left: number, right: number): void {
8    while (left >= 0 && right < s.length && s[left] === s[right]) {
9      const len = right - left + 1;

String Compression

1function compress(chars: string[]): number {
2  let write = 0;
3  let read = 0;
4  
5  while (read < chars.length) {
6    const char = chars[read];
7    let count = 0;
8    
9    // Count consecutive characters
10    while (read < chars.length && chars[read] === char) {
11      read++;
12      count++;
13    }
14    
15    // Write character
16    charswrite  char

Valid Parentheses

1function isValid(s: string): boolean {
2  const stack: string[] = [];
3  const pairs: { [key: string]: string } = {
4    ')': '(',
5    '}': '{',
6    ']': '['
7  };
8  
9  for (const char of s) {
10    if (char in pairs) {
11      // Closing bracket
12      if stacklength    stack  pairschar

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:

1// Using built-in methods
2function reverseString(s: string): string {
3  return s.split('').reverse().join('');
4}
5
6// In-place (using array)
7function reverseStringInPlace(s: string[]): void {
8  let left = 0;
9  let right = s.length - 1;
10  
11  while (left < right) {
12    [s[left sright  sright sleft

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:

1// Approach 1: Sorting
2function isAnagramSort(s1: string, s2: string): boolean {
3  if (s1.length !== s2.length) return false;
4  return s1.split('').sort().join('') === s2.split('').sort().join('');
5}
6// Time: O(n log n), Space: O(n)
7
8// Approach 2: Character counting (optimal)
9function isAnagramOptimals1  s2

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

• 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