Strings & Pattern Matching - Data Structures & Algorithms

A string is really just an array of characters. Under the hood, "hello" is stored as ['h', 'e', 'l', 'l', 'o']. This means most array techniques (two pointers, sliding window, hashing) work on strings too.

The big catch? In some languages, strings are immutable — we can’t change them in place. Every time we “modify” a string, we’re actually creating a brand new one.

String Immutability

This is one of those things that trips people up in interviews. Let’s be clear about which languages do what:

Language	Mutable?	What happens on “modification”
JavaScript	Immutable	Creates a new string
Python	Immutable	Creates a new string
Java	Immutable (`String`), Mutable (`StringBuilder`)	`String` creates new, `StringBuilder` modifies in place

Why does this matter? Because concatenating strings in a loop is O(n²) in immutable languages. Each concatenation creates a new string and copies everything over.

// BAD — O(n²) because strings are immutable
let result = "";
for (let i = 0; i < 1000; i++) {
  result += "a"; // creates a new string every time!
}

// GOOD — use array and join at the end
const parts = [];
for (let i = 0; i < 1000; i++) {
  parts.push("a");
}
const result2 = parts.join(""); // one allocation

# BAD — O(n²) because strings are immutable
result = ""
for i in range(1000):
    result += "a"  # creates a new string every time!

# GOOD — use list and join at the end
parts = []
for i in range(1000):
    parts.append("a")
result2 = "".join(parts)  # one allocation

// BAD — O(n²) with String
String result = "";
for (int i = 0; i < 1000; i++) {
    result += "a"; // creates a new String every time!
}

// GOOD — use StringBuilder
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 1000; i++) {
    sb.append("a"); // modifies in place
}
String result2 = sb.toString(); // one allocation

Palindrome Check

A palindrome reads the same forwards and backwards. “racecar” is a palindrome. “hello” is not.

The classic approach: two pointers — one at the start, one at the end. If they always match as they walk inward, it’s a palindrome.

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello"));   // false

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

public static boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}
// "racecar" → true, "hello" → false

Time: O(n), Space: O(1) — we just walk from both ends.

Interview tip: If the problem says “consider only alphanumeric characters and ignore case,” we add a check to skip non-alphanumeric characters and compare lowercase versions. This is LeetCode 125 — Valid Palindrome.

Anagram Detection

Two strings are anagrams if they contain the exact same characters, just rearranged. “listen” and “silent” are anagrams. “hello” and “world” are not.

The idea: count the frequency of each character in both strings. If the counts match, they’re anagrams.

function isAnagram(s, t) {
  if (s.length !== t.length) return false;

  const freq = {};
  for (const ch of s) freq[ch] = (freq[ch] || 0) + 1;
  for (const ch of t) {
    if (!freq[ch]) return false; // char not found or count is 0
    freq[ch]--;
  }
  return true;
}

console.log(isAnagram("listen", "silent")); // true
console.log(isAnagram("hello", "world"));   // false

def is_anagram(s, t):
    if len(s) != len(t):
        return False

    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    for ch in t:
        if freq.get(ch, 0) == 0:
            return False  # char not found or count is 0
        freq[ch] -= 1
    return True

print(is_anagram("listen", "silent"))  # True
print(is_anagram("hello", "world"))    # False

public static boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    int[] freq = new int[26]; // assuming lowercase a-z
    for (char ch : s.toCharArray()) freq[ch - 'a']++;
    for (char ch : t.toCharArray()) {
        freq[ch - 'a']--;
        if (freq[ch - 'a'] < 0) return false;
    }
    return true;
}
// "listen", "silent" → true

Time: O(n), Space: O(1) — the frequency map has at most 26 keys (for lowercase English letters), so space is constant.

Character Frequency Counting

Counting how often each character appears is the backbone of tons of string problems. Let’s use it to find the first non-repeating character — a classic interview question.

function firstNonRepeating(s) {
  const freq = {};
  for (const ch of s) freq[ch] = (freq[ch] || 0) + 1;

  // second pass: find first char with count 1
  for (let i = 0; i < s.length; i++) {
    if (freq[s[i]] === 1) return i;
  }
  return -1; // all characters repeat
}

console.log(firstNonRepeating("aabbcdd")); // 4 (index of 'c')
console.log(firstNonRepeating("aabb"));    // -1

def first_non_repeating(s):
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1

    # second pass: find first char with count 1
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return i
    return -1  # all characters repeat

print(first_non_repeating("aabbcdd"))  # 4 (index of 'c')
print(first_non_repeating("aabb"))     # -1

public static int firstNonRepeating(String s) {
    int[] freq = new int[26];
    for (char ch : s.toCharArray()) freq[ch - 'a']++;

    // second pass: find first char with count 1
    for (int i = 0; i < s.length(); i++) {
        if (freq[s.charAt(i) - 'a'] == 1) return i;
    }
    return -1; // all characters repeat
}
// "aabbcdd" → 4 (index of 'c')

Time: O(n), Space: O(1) — two passes through the string, fixed-size frequency map.

Common String Patterns in Interviews

Here’s a cheat sheet of what technique to reach for based on the problem type:

Problem Type	Go-To Technique
Palindrome check	Two pointers (start + end)
Anagram check / grouping	Character frequency map
Substring search	Sliding window
First unique / most frequent char	Frequency counting
String reversal	Two pointers
Longest substring without repeats	Sliding window + hash set
Pattern matching (exact)	KMP or Rabin-Karp (advanced)

String Comparison Gotcha

One thing that bites people in Java: never compare strings with ==. The == operator compares memory addresses, not content. Always use .equals().

// JavaScript — === works fine for strings
const a = "hello";
const b = "hello";
console.log(a === b); // true (compares values)

# Python — == works fine for strings
a = "hello"
b = "hello"
print(a == b)  # True (compares values)

// Java — NEVER use == for strings!
String a = new String("hello");
String b = new String("hello");
System.out.println(a == b);      // false (compares references!)
System.out.println(a.equals(b)); // true (compares content)

In simple language, strings are arrays with a personality. The immutability thing is the big gotcha — always think about whether we’re creating new strings when we modify them. For interview problems, the frequency map is our best friend. If we need to count characters, check for anagrams, or find unique characters, a hash map with character counts is almost always the way to go.