Strings in Data Structures & Algorithms: Complete Guide

Master string manipulation, pattern matching, and algorithm optimization. This tutorial covers string operations, encoding techniques, and common interview patterns with implementation examples.

String Operation Distribution in Real Systems

Search (35%)

Comparison (25%)

Transformation (20%)

Encoding (20%)

1. String Fundamentals

Core Characteristics:

Immutable: Original string cannot be changed (in most languages)
Character Encoding: ASCII (1 byte), Unicode (2-4 bytes)
Null-terminated: C-style strings end with '\0'

Time Complexities:

Operation	Time	Space
Access	O(1)	O(1)
Concatenation	O(n+m)	O(n+m)
Substring	O(k)	O(k)
Search (naive)	O(n*m)	O(1)

Basic Implementation:


// String reversal
function reverseString(str) {
  return str.split('').reverse().join('');
}

// Palindrome check
function isPalindrome(str) {
  const cleaned = str.replace(/[^a-z0-9]/gi, '').toLowerCase();
  return cleaned === reverseString(cleaned);
}

2. String Manipulation Patterns

Essential Techniques:

Two Pointers


// Remove duplicates in-place
function removeDuplicates(str) {
  const chars = str.split('');
  let slow = 0;
  
  for (let fast = 0; fast < chars.length; fast++) {
    if (chars[fast] !== chars[slow]) {
      chars[++slow] = chars[fast];
    }
  }
  
  return chars.slice(0, slow + 1).join('');
}

Sliding Window


// Longest substring without repeating characters
function longestUniqueSubstring(s) {
  const map = new Map();
  let max = 0, start = 0;
  
  for (let end = 0; end < s.length; end++) {
    if (map.has(s[end])) {
      start = Math.max(start, map.get(s[end]) + 1);
    }
    map.set(s[end], end);
    max = Math.max(max, end - start + 1);
  }
  
  return max;
}

Common Problem Types:

Anagram Detection: Frequency counting
String Compression: Run-length encoding
Parentheses Validation: Stack-based
Pattern Matching: KMP algorithm

3. Advanced String Algorithms

Pattern Matching:

Knuth-Morris-Pratt (KMP)


// Build LPS array for KMP
function computeLPS(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0, i = 1;
  
  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      lps[i++] = ++len;
    } else {
      if (len !== 0) len = lps[len - 1];
      else lps[i++] = 0;
    }
  }
  
  return lps;
}

Rabin-Karp (Rolling Hash)


// Rolling hash implementation
function rabinKarp(text, pattern) {
  const prime = 101;
  const d = 256;
  const M = pattern.length;
  const N = text.length;
  let p = 0, t = 0, h = 1;
  
  // Calculate hash value for pattern and first window
  for (let i = 0; i < M; i++) {
    p = (d * p + pattern.charCodeAt(i)) % prime;
    t = (d * t + text.charCodeAt(i)) % prime;
    if (i < M - 1) h = (h * d) % prime;
  }
  
  // Slide the pattern over text
  for (let i = 0; i <= N - M; i++) {
    if (p === t) {
      // Check characters one by one
      let j;
      for (j = 0; j < M; j++) {
        if (text[i + j] !== pattern[j]) break;
      }
      if (j === M) return i;
    }
    
    // Calculate hash for next window
    if (i < N - M) {
      t = (d * (t - text.charCodeAt(i) * h) + 
           text.charCodeAt(i + M)) % prime;
      if (t < 0) t += prime;
    }
  }
  
  return -1;
}

String Problem-Solving Cheat Sheet

Problem Type	Technique	Time Complexity
Anagram Detection	Frequency Count	O(n)
Longest Common Substring	Dynamic Programming	O(m*n)
Pattern Matching	KMP Algorithm	O(n+m)
String Compression	Two Pointers	O(n)

4. String Encoding & Storage

Unicode Handling

UTF-8/16 encoding challenges


// Counting Unicode characters
function countUnicodeChars(str) {
  return [...str].length; // Spread handles surrogate pairs
}

Trie Structures

Prefix trees for string storage


class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

Run-Length Encoding

Basic compression technique


function runLengthEncode(str) {
  let result = '';
  let count = 1;
  
  for (let i = 1; i <= str.length; i++) {
    if (i < str.length && str[i] === str[i - 1]) {
      count++;
    } else {
      result += str[i - 1] + count;
      count = 1;
    }
  }
  
  return result;
}

String Problem-Solving Checklist

✓ Handle empty string and single character cases

✓ Consider case sensitivity and Unicode

✓ Optimize for time vs space constraints

✓ Test edge cases (spaces, punctuation, numbers)

Algorithm Expert Insight: String manipulation accounts for 30% of technical interview questions. Mastering pattern matching and two-pointer techniques can significantly improve problem-solving efficiency.

0 Interaction

0 Views

0 Likes