String

Notes and typical questions for String related problems

Notes

• In Java, When joining String, new StringBuilder(s1).append(s2).toString() is faster than s1 + s2

Typical Questions

String Manipulation

• 🌟 LC 344. Reverse String

• LC 541. Reverse String II

• 🌟 ⚪ LC 151. Reverse Words in a String

  • The most important part is how to efficiently remove leading/trailing spaces and duplicate spaces between words. Make that logic simple enough!

  • Optimal Answer

• Other platforms: Right shift of a string

  • It's not difficult, once you find the approach

• LC 1768. Merge Strings Alternately

• LC 345. Reverse Vowels of a String

• LC 443. String Compression

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• LC 67. Add Binary

  • Optimal Answer. TC: $O(n)$, SC: $O(n)$

• 🔴 LC 761. Special Binary String

  • Super hard to understand question...

  • Optimal Answer. TC: $O(n^2)$, SC: $O(n)$

KMP

• Notes: the most important part is calculating next[]

• 🌟 🟠 LC 28. Find the Index of the First Occurrence in a String

  • Assume the length of haystack is n and the length of needle is m

  • Optimal Answer. TC: $O(m+n)$, SC: $O(m)$

• LC 459. Repeated Substring Pattern

  • A tricky way using next[] of KMP + Mathematical induction

String property

• 🔴 LC 1071. Greatest Common Divisor of Strings

  • Check answer https://leetcode.com/problems/greatest-common-divisor-of-strings/solutions/4470356/easy-clear-and-no-ambiguity-proof-based-on-editorial-ver/

    • if str1 + str2 != str2 + str1, there must be no gcd string. It's easy to prove.

    • if str1 + str2 == str2 + str1, the divisible string must exist,

      • if the divisible string exists, it must be a prefix of either str1 or str2

      • if the divisible string exists, the gcd string length must be the gcd of str1 length and str2 length

• ⚪ LC 14. Longest Common Prefix

  • Optimal Solution.

  • Let $n$ be the number of strings, $m$ be the minimum length of all strings

    • TC: $O(n*m)$

    • SC: $(1)$

• 🔴 LC 2663. Lexicographically Smallest Beautiful String

  • Understandable Answer. TC: $O(n^2*k)$, SC: $O(n)$

  • Reference: https://leetcode.com/problems/lexicographically-smallest-beautiful-string/solutions/3468265

• ⚪ LC 125. Valid Palindrome

  • Ease of making mistakes during implementation

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• LC 3110. Score of a String

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• ⚪ LC 1422. Maximum Score After Splitting a String

  • The one-pass solution is really beautiful! I didn't realize this problem could be resolved using a one-pass solution when I wrote my own answer with the same TC.

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• 🔴 LC 336. Palindrome Pairs

  • Read that good editorial carefully...

  • Optimal Answer.

    • Let $n$ be the number of words and $k$ be the max length of single word

    • TC: $O(k^2*n)$

    • SC: $O(k*n+k^2+n^2)$

String Traversal

• ⚪ LC 6. Zigzag Conversion

  • Optimal Solution. TC: $O(n)$, SC: $O(1)$

• ⚪ LC 8. String to Integer (atoi)

  • Optimal Solution. TC: $O(n)$, SC: $O(1)$

• ⚪ LC 58. Length of Last Word

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• ⚪ LC 3136. Valid Word

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

Simulation

• ⚪ LC 68. Text Justification

  • Optimal Answer.

    • Let $n$ be words.length, $k$ be the average length of a word, and $m$ be maxWidth

    • TC: $O(n*k)$

    • SC: $O(m)$

• LC 412. Fizz Buzz

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$