Skip to content

README.md

Latest commit

 

History

History
142 lines (116 loc) · 12 KB

README.md

File metadata and controls

142 lines (116 loc) · 12 KB
Raw

03 - Strings and Hashing

PHASE 3 — STRINGS + HASHING (111–170)

Topics Covered

  • String Manipulation
  • Hash Tables & Hash Maps
  • Character Frequency Analysis
  • Pattern Matching (KMP, Rabin-Karp, Z-Algorithm)
  • Anagrams & Permutations
  • Palindromes
  • String Parsing & Conversion
  • Parenthesis Matching
  • String Compression
  • Encoding/Decoding

Problems List

No. Problem Difficulty Topics Link
1 Valid Anagram Easy Hash Table, String Open
2 Ransom Note Easy Hash Table, String Open
3 Isomorphic Strings Easy Hash Table, String Open
4 Word Pattern Easy Hash Table, String Open
5 Happy Number Easy Hash Table, Math Open
6 First Unique Character in a String Easy Hash Table, String Open
7 Find the Difference Easy Hash Table, String Open
8 Longest Palindrome Easy Hash Table, String Open
9 Roman to Integer Easy String, Math Open
10 Reverse Integer Easy String, Math Open
11 Valid Palindrome Easy String, Two Pointer Open
12 Reverse Vowels of a String Easy String, Two Pointer Open
13 Backspace String Compare Easy String, Stack Open
14 Buddy Strings Easy String, Hash Table Open
15 Bulls and Cows Easy String, Hash Table Open
16 Goat Latin Easy String Open
17 Reverse Words in a String Easy String Open
18 String Compression Easy String Open
19 Check Inclusion Easy Sliding Window, Hash Table Open
20 Remove Adjacent Duplicates In String Easy String, Stack Open
21 Group Anagrams Medium Hash Table, String Open
22 Top K Frequent Elements Medium Hash Table, Heap Open
23 Encode and Decode Strings Medium Hash Table, String, Design Open
24 Valid Sudoku Medium Hash Table, Matrix Open
25 Integer to Roman Medium String, Math Open
26 String to Integer (atoi) Medium String, Math Open
27 Valid Palindrome II Medium String, Two Pointer Open
28 Longest Common Prefix Medium String Open
29 Implement strStr() Medium String, Pattern Matching Open
30 Count and Say Medium String, Simulation Open
31 Zigzag Conversion Medium String, Simulation Open
32 Compare Version Numbers Medium String, Parsing Open
33 Add Binary Medium String, Math Open
34 Multiply Strings Medium String, Math Open
35 Decode String Medium String, Stack Open
36 Remove Duplicate Letters Medium String, Stack, Greedy Open
37 Reorganize String Medium String, Hash Table, Heap Open
38 Longest Palindromic Substring Medium String, Two Pointer, DP Open
39 Palindromic Substrings Medium String, Two Pointer, DP Open
40 Minimum Add to Make Parentheses Valid Medium String, Stack Open
41 Longest Happy Prefix Medium String, KMP Open
42 Repeated Substring Pattern Medium String, KMP Open
43 Custom Sort String Medium String, Hash Table Open
44 Count Distinct Subsequences Medium String, DP Open
45 Partition Labels Medium String, Two Pointer, Hash Table Open
46 Lexicographically Smallest Equivalent String Medium String, Union-Find Open
47 Basic Calculator Hard String, Stack, Parsing Open
48 Remove Invalid Parentheses Hard String, BFS, DFS Open
49 Rabin Karp Algorithm Hard String, Hash, Pattern Matching Open
50 KMP Algorithm Hard String, Pattern Matching Open
51 Z Algorithm Hard String, Pattern Matching Open
52 Shortest Palindrome Hard String, KMP, Palindrome Open
53 Longest Prefix Suffix Hard String, KMP Open
54 TinyURL Encoder Hard String, Hash Table, Design Open
55 Valid Parenthesis String Hard String, DP, Greedy Open
56 Score of Parentheses Hard String, Stack Open
57 Decode Ways Hard String, DP Open
58 Simplify Path Hard String, Stack Open
59 Interleaving String Hard String, DP Open
60 Minimum Deletions to Make Frequencies Unique Hard String, Hash Table, Greedy Open

Important Patterns

Hash Table Fundamentals

  • Use HashMap/HashSet for O(1) lookups
  • Track character/element frequencies efficiently
  • Two-map pattern for bijective relationships (Isomorphic Strings)

Anagram & Permutation Patterns

  • Frequency matching via sorted strings or character counts
  • Group anagrams by canonical form
  • Check permutation equality with character frequency

Pattern Matching Algorithms

  • KMP (Knuth-Morris-Pratt): Build failure function, O(n+m) search
  • Rabin-Karp: Rolling hash for efficient pattern matching
  • Z-Algorithm: Build Z-array for linear pattern matching

Palindrome Patterns

  • Expand around center: O(n²) time, O(1) space
  • Dynamic Programming: O(n²) time and space
  • Manacher's Algorithm: O(n) linear time

String Parsing & Conversion

  • Handle edge cases: overflow, signs, whitespace
  • State machines for complex parsing (atoi, calculator)
  • Stack-based approach for nested structures

Parenthesis/Bracket Patterns

  • Stack for matching validation
  • Greedy approaches for removal problems
  • DP for optimal/distinct solutions

Greedy String Optimization

  • Remove duplicate letters while maintaining frequency
  • Lexicographically smallest string construction
  • Trade-off analysis between removal and result quality

Dynamic Programming on Strings

  • Edit Distance/Levenshtein: Compare two strings
  • Interleaving: Check if string is interleaving of two others
  • Decode Ways: Count valid decodings with variable-length rules
  • Partition: Decode with specific delimiters

String Encoding/Decoding

  • Serialization format design (TinyURL, Encode/Decode)
  • Bidirectional transformations
  • Handle edge cases and special characters