String algorithms — palindrome, anagram, substring search

Intermediate5 min read·eng-08-006

interview

Concept

String algorithms — problems involving character arrays, substrings, and pattern matching appear frequently in PHP development and interviews.

Palindrome: A string that reads the same forward and backward. Check: two-pointer from both ends. Expand around center for longest palindromic substring.

Anagram: Two strings with the same characters in possibly different order. Check: sort both and compare (O(n log n)), OR count character frequencies and compare (O(n)).

Substring search:

Naive: O(n × m) — for each position in the haystack, check if needle matches.
strpos() in PHP: Highly optimized C, but worst case O(n × m).
KMP (Knuth-Morris-Pratt): O(n + m) — precomputes a failure function to avoid backtracking.
str_contains(), str_starts_with(), str_ends_with() (PHP 8.0+): Prefer these for simple checks.

PHP string functions (all important to know):

strlen(): Length in bytes. Use mb_strlen() for multibyte (UTF-8).
substr(): Slice. Use mb_substr() for multibyte.
str_replace(): Replace all occurrences.
preg_match() / preg_replace(): Regex-based.
explode() / implode(): Split/join.
strtolower() / strtoupper(): Case. Use mb_* variants for UTF-8.
trim() / ltrim() / rtrim(): Remove whitespace.
str_word_count(): Count words.
similar_text() / levenshtein(): String similarity/distance.

String immutability in PHP: PHP strings are immutable in practice (assigning to $str[0] creates a copy). Concatenation in a loop is O(n²) — use arrays + implode() for large string building.

Code Example

php

<?php
// Palindrome check — O(n)
function isPalindrome(string $s): bool
{
    $s = strtolower(preg_replace('/[^a-z0-9]/i', '', $s));
    return $s === strrev($s);
}

// Anagram check — O(n) using character count
function isAnagram(string $a, string $b): bool
{
    if (strlen($a) !== strlen($b)) return false;
    $count = array_fill_keys(str_split($a), 0);
    foreach (str_split($a) as $c) $count[$c]++;
    foreach (str_split($b) as $c) {
        if (!isset($count[$c]) || --$count[$c] < 0) return false;
    }
    return true;
}

echo isAnagram('listen', 'silent'); // true
echo isAnagram('hello', 'world');   // false

// Group anagrams — O(n × k log k) where k = max string length
function groupAnagrams(array $words): array
{
    $groups = [];
    foreach ($words as $word) {
        $key           = str_split($word);
        sort($key);
        $groups[implode('', $key)][] = $word;
    }
    return array_values($groups);
}

$grouped = groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']);
// [['eat','tea','ate'], ['tan','nat'], ['bat']]

// Reverse words in a sentence — O(n)
function reverseWords(string $sentence): string
{
    return implode(' ', array_reverse(array_filter(explode(' ', $sentence))));
}
echo reverseWords('the sky is blue'); // 'blue is sky the'

// Efficient string building — O(n) using array + implode
function buildLargeString(int $n): string
{
    $parts = [];
    for ($i = 0; $i < $n; $i++) {
        $parts[] = "item{$i}"; // O(1) array append
    }
    return implode(', ', $parts); // O(n) single pass
    // Avoid: $str .= "item{$i}"; — O(n²) total for large n (copies growing string each time)
}

// Levenshtein distance — minimum edits to transform a to b
echo levenshtein('kitten', 'sitting'); // 3
echo similar_text('Hello', 'World');   // returns number of matching chars

// PHP 8+ clean string checks
$url = 'https://example.com/api/users';
echo str_starts_with($url, 'https://'); // true
echo str_ends_with($url, 'users');      // true
echo str_contains($url, '/api/');       // true

// Multibyte safe operations for UTF-8
$emoji = 'Hello 🌍';
echo strlen($emoji);     // bytes (wrong for char count with emoji)
echo mb_strlen($emoji);  // 8 (correct character count)

PreviousTwo-pointer and sliding window — common interview patternsAlgorithms in PHP NextHow does PHP execute code? Parsing → AST → opcode → zend_executeSenior Interview Prep — PHP