Visualized DSA Strategies

Episode 6 Strings

1 h 10 min · PHP · Quiz

Title card of Episode 6: Strings

▶ This video is coming to YouTube soon.

The complete guide to strings in PHP interviews. First how PHP strings really work: rows of bytes you can change in place, characters as numbers with ord and chr, why $s = $s . $c in a loop is O(n²) while .= grows the string in place, the toolbox for building strings with .=, arrays and implode, what every common function costs, and five traps that catch everyone. Then nine techniques, each worked as a small problem in full: examples, the brute force animated beside the running line of code, the complete code, every line explained, and the better solution the same way.

What you'll learn

  • How a PHP string is stored, and what strlen, $s[$i], substr, === and strpos cost
  • Characters are numbers: ord($c) − 97 for letter counts, ord($c) − 48 for digits
  • Why $s = $s . $c in a loop is O(n²), and how .= grows the string in place
  • Counting letters in 26 slots, and two pointers from both ends
  • Mapping letters both ways with arrays, and an array used as a stack
  • Adding huge numbers digit by digit, and counting words with explode and an array
  • Expanding palindromes from their centre, and finding a pattern with a rolling hash (the idea behind Rabin–Karp)
  • Five traps: == on numeric strings, strpos returning 0, + on strings, substr's length, strlen counting bytes
  • How to spot which technique a problem wants

Chapters

  1. 0:00Intro
  2. 0:21What's a string?
  3. 1:29Characters are numbers
  4. 2:35Character codes worth knowing
  5. 3:22PHP strings can change
  6. 4:14Why $s = $s . $c is O(n²)
  7. 5:16.= grows the string in place
  8. 6:37The PHP string toolbox
  9. 7:54What string functions cost
  10. 8:36Five traps
  11. 9:38Nine string techniques
  12. 10:17Type 1 · Compress runs of letters
  13. 16:48Type 2 · First unique character
  14. 22:34Type 3 · Is it a palindrome?
  15. 28:15Type 4 · Same pattern?
  16. 34:05Type 5 · Remove adjacent duplicates
  17. 40:31Type 6 · Add two number strings
  18. 48:32Type 7 · Most common word
  19. 54:45Type 8 · Longest odd palindrome
  20. 1:01:29Type 9 · Find a word in a text
  21. 1:08:00Spot the technique
  22. 1:08:50Quiz: which technique?
  23. 1:09:38Recap

Quiz: test yourself

The 5 questions from the end of the episode. Pick an answer to see why it's right.