Visualized DSA Strategies

Episode 6 Strings

1 h 8 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 strings really work: characters are numbers, a string can never change, why += in a loop is O(n²) and how a StringBuilder makes it O(n) by linking on new blocks instead of copying, what every common member costs (Substring takes a length, not an end), 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 string is stored, and what the indexer, Substring, == and IndexOf cost
  • Characters are numbers: c − 'a' for letter counts, c − '0' for digits
  • Immutability, why += in a loop is O(n²), and the StringBuilder toolbox: Append, Remove, Insert, ToString
  • Counting letters with int[26], and two pointers from both ends
  • Mapping letters both ways with two Dictionaries, and a StringBuilder used as a stack
  • Adding huge numbers digit by digit, and counting words with Split and a Dictionary
  • 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:30Characters are numbers
  4. 2:26Character codes worth knowing
  5. 3:07Strings can't change
  6. 3:52Why += in a loop is O(n²)
  7. 4:43StringBuilder: add in place
  8. 5:40The StringBuilder toolbox
  9. 6:59What string methods cost
  10. 7:38Five traps
  11. 8:34Nine string techniques
  12. 9:12Type 1 · Compress runs of letters
  13. 15:28Type 2 · First unique character
  14. 21:02Type 3 · Is it a palindrome?
  15. 27:07Type 4 · Same pattern?
  16. 33:05Type 5 · Remove adjacent duplicates
  17. 39:21Type 6 · Add two number strings
  18. 46:51Type 7 · Most common word
  19. 52:55Type 8 · Longest odd palindrome
  20. 59:32Type 9 · Find a word in a text
  21. 1:05:50Spot the technique
  22. 1:06:35Quiz: which technique?
  23. 1:07:23Recap

Quiz: test yourself

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