Visualized DSA Strategies

Episode 6 Strings

1 h 9 min · C++ · Quiz

Title card of Episode 6: Strings

▶ This video is coming to YouTube soon.

The complete guide to strings in C++ interviews. First how std::string really works: characters are numbers, a C++ string can change in place, why res += c is amortised O(1) while res = res + c copies the whole string and makes a loop O(n²), what every common operation costs (substr, string_view, find, to_string, stoi), 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 std::string is stored, and what size, s[i], substr, == and find cost
  • Characters are numbers: c − 'a' for letter counts, c − '0' for digits
  • A mutable string: why s = s + c in a loop is O(n²), why s += c is O(n), and reserve
  • Counting letters with vector<int>(26), and two pointers from both ends
  • Mapping letters both ways, and a string used as a stack with push_back and pop_back
  • Adding huge numbers digit by digit, and counting words with an unordered_map
  • 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:20What's a string?
  3. 1:19Characters are numbers
  4. 2:16Character codes worth knowing
  5. 2:59Strings can change
  6. 3:52Why res = res + c is O(n²)
  7. 4:45res += c: add in place
  8. 5:44The std::string toolbox
  9. 6:56What string operations cost
  10. 7:40Five traps
  11. 8:34Nine string techniques
  12. 9:13Type 1 · Compress runs of letters
  13. 15:42Type 2 · First unique character
  14. 21:31Type 3 · Is it a palindrome?
  15. 27:23Type 4 · Same pattern?
  16. 33:19Type 5 · Remove adjacent duplicates
  17. 39:43Type 6 · Add two number strings
  18. 47:15Type 7 · Most common word
  19. 53:34Type 8 · Longest odd palindrome
  20. 1:00:10Type 9 · Find a word in a text
  21. 1:06:28Spot the technique
  22. 1:07:14Quiz: which technique?
  23. 1:08:01Recap

Quiz: test yourself

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