Visualized DSA Strategies

Episode 6 Strings

1 h 6 min · Python · Quiz

Title card of Episode 6: Strings

▶ This video is coming to YouTube soon.

The complete guide to strings in Python interviews. First how a str really works: characters are numbers (ord and chr), a str can never change, why += in a loop is O(n²) by the rules even though CPython often grows the string in place, why a list and one "".join is O(n) in any Python, what every common operation costs (a slice copies), 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 str is stored, and what len, s[i], slices, == and find cost
  • Characters are numbers: ord(c) − ord('a') for letter counts, ord(c) − ord('0') for digits
  • Immutability, why += in a loop can be O(n²) (and why CPython often hides it), and building with a list and "".join
  • Counting letters with a list of 26, and two pointers from both ends
  • Mapping letters both ways with two dicts, and a list used as a stack
  • Adding huge numbers digit by digit, and counting words with split and a dict
  • Expanding palindromes from their centre
  • Finding a pattern with a rolling hash (the idea behind Rabin–Karp)
  • How to spot which technique a problem wants

Chapters

  1. 0:00Intro
  2. 0:21What's a string?
  3. 1:18Characters are numbers
  4. 2:21Character codes worth knowing
  5. 3:02Strings can't change
  6. 3:50Why += in a loop can be O(n²)
  7. 4:48A list: add in place
  8. 5:42The list-of-characters toolbox
  9. 6:43What str operations cost
  10. 7:18Five traps
  11. 8:07Nine string techniques
  12. 8:46Type 1 · Compress runs of letters
  13. 14:50Type 2 · First unique character
  14. 20:31Type 3 · Is it a palindrome?
  15. 26:07Type 4 · Same pattern?
  16. 31:56Type 5 · Remove adjacent duplicates
  17. 37:51Type 6 · Add two number strings
  18. 45:47Type 7 · Most common word
  19. 51:39Type 8 · Longest odd palindrome
  20. 58:03Type 9 · Find a word in a text
  21. 1:04:18Spot the technique
  22. 1:05:06Quiz: which technique?
  23. 1:05:54Recap

Quiz: test yourself

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