string
006.ZigZag-Conversion (M+) 336.Palindrome-Pairs (H-) 388.Longest-Absolute-File-Path (M+) 408.Valid-Word-Abbreviation (M) 411.Minimum-Unique-Word-Abbreviation (H) 418.Sentence-Screen-Fitting (M+) 423.Reconstruct-Original-Digits-from-English (H-) 527.Word-Abbreviation (M+) 556.Next Greater Element III (H-) 616.Add-Bold-Tag-in-String (M) 467.Unique-Substrings-in-Wraparound-String (H-) 564.Find-the-Closest-Palindrome (H) 722.Remove-Comments (H) 736.Parse-Lisp-Expression (H-) 816.Ambiguous-Coordinates (M+) 844.Backspace-String-Compare (M+) 1616.Split-Two-Strings-to-Make-Palindrome (M+) 1754.Largest-Merge-Of-Two-Strings (M+) 1849.Splitting-a-String-Into-Descending-Consecutive-Values (M+)
Rolling Hash
1044.Longest-Duplicate-Substring (H) 1062.Longest-Repeating-Substring (H-) 1554.Strings-Differ-by-One-Character (H) 1698.Number-of-Distinct-Substrings-in-a-String (H-) 1923.Longest-Common-Subpath (H)
KMP
1392.Longest-Happy-Prefix (H) 028.Implement-strStr (H) 214.Shortest-Palindrome (H) 459.Repeated-Substring-Pattern (H) 572.Subtree-of-Another-Tree (H) 1367.Linked-List-in-Binary-Tree (H) 1397.Find All Good Strings (TBD) 1764.Form-Array-by-Concatenating-Subarrays-of-Another-Array (H)
Manacher
005.Longest-Palindromic-Substring (H) 214.Shortest-Palindrome (H) 647.Palindromic-Substrings (M+) 1960.Maximum-Product-of-the-Length-of-Two-Palindromic-Substrings (H)
Palindrome
Several ways to solve the Longest palindrome substring problem
DP-based solution: O(n^2) space and time, if need to storing palindrome result, this is always better (e.g. palindrome partitioning)
Start looping from middle: O(n^2) time
Manacher's algorithm: O(n) time, not generic enough.
https://expl.ai/APDFXTD
String corner cases:
Whether there will be overlapping
Whether sources/indexes will be sorted
Last updated