šŸ”¤ Strings - Text Processing

šŸŸ¢ Beginner Linear DS 45 min read

šŸŽÆ What is a String?

A String is a sequence of characters treated as a single data type. In computer science, strings are essentially character arrays with special properties and operations. String manipulation is one of the most frequently tested topics in coding interviews.

šŸ“ String Properties in PHP

šŸ”‘ Key Characteristics
  • Immutable in many languages (not PHP)
  • Zero-indexed character access
  • Can contain any character (Unicode)
  • Length can vary dynamically
  • Common operations: search, slice, concat, replace
āš” PHP String Access
$str = "Hello";
echo $str[0];    // H
echo $str[-1];   // o (PHP 7.1+)
echo strlen($str); // 5
$str[0] = 'J';   // "Jello" (mutable!)

āš™ļø Core String Algorithms

1. Palindrome Check (O(n))

function isPalindrome(string $s): bool {
    $left = 0; $right = strlen($s) - 1;
    while ($left < $right) {
        if ($s[$left] !== $s[$right]) return false;
        $left++; $right--;
    }
    return true;
}
var_dump(isPalindrome("racecar")); // true
var_dump(isPalindrome("hello"));   // false

2. Reverse String (O(n))

// Using PHP built-in
$reversed = strrev("DSA Mastery"); // "yertsaM ASD"

// Manual implementation
function reverseString(string $s): string {
    $result = '';
    for ($i = strlen($s) - 1; $i >= 0; $i--) {
        $result .= $s[$i];
    }
    return $result;
}

3. Substring Search - strpos vs KMP

// PHP built-in (uses Boyer-Moore internally): O(n+m) avg
$pos = strpos("hello world", "world"); // 6

// Naive approach: O(n*m)
function naiveSearch(string $text, string $pattern): int {
    $n = strlen($text); $m = strlen($pattern);
    for ($i = 0; $i <= $n - $m; $i++) {
        $j = 0;
        while ($j < $m && $text[$i+$j] === $pattern[$j]) $j++;
        if ($j === $m) return $i;
    }
    return -1;
}

4. Character Frequency Count (O(n))

function charFrequency(string $s): array {
    $freq = [];
    for ($i = 0; $i < strlen($s); $i++) {
        $c = $s[$i];
        $freq[$c] = ($freq[$c] ?? 0) + 1;
    }
    return $freq;
}
// Or: $freq = array_count_values(str_split($s));

5. Anagram Check (O(n))

function isAnagram(string $s1, string $s2): bool {
    if (strlen($s1) !== strlen($s2)) return false;
    return array_count_values(str_split($s1))
        === array_count_values(str_split($s2));
}
var_dump(isAnagram("listen", "silent")); // true

šŸ“Š Complexity Reference

Operation Time PHP Function
Access char by index O(1) $str[$i]
Length O(1) strlen()
Concatenation O(n+m) .= operator
Substring O(k) substr()
Search (naive) O(n*m) Manual loop
Search (built-in) O(n+m) strpos()
Replace O(n) str_replace()
Split O(n) explode()

šŸ’¼ Interview Questions

ctype_digit($str) or preg_match('/^\d+$/', $str). Both O(n).

Use hash map for frequency, then scan for first char with count=1. O(n) time, O(1) space (26 letters max).

Expand Around Center: For each position, expand outward while characters match. O(nĀ²) time, O(1) space. Or use Manacher's Algorithm for O(n).

šŸ“ Quick Quiz

Q1: What is the time to access a character by index in a PHP string?

Q2: "listen" and "silent" are:

Q3: What does strpos("hello", "ll") return?

Q4: In-place string reversal of "abcd" requires swapping:

Q5: Which algorithm finds all occurrences of a pattern in text in O(n+m)?

šŸ“‹ Cheat Sheet

Palindrome reads same forwards/backwards Two-pointer: O(n)
Anagram Same chars, different order Frequency map: O(n)
Substring Contiguous sequence substr(), strpos()
Subsequence Sequence (not necessarily contiguous) Two-pointer matching: O(n)
strlen() String length O(1) in PHP
Previous: Arrays Next: Recursion