ajdevhub
    Learning Portal » String

    📑 Table of Contents

    1. 📘 DSA: Strings Learning Roadmap (Beginner → Advanced) 1.1. 1. Basics of Strings (Foundations) 1.2. 🔍 2. Two Pointers on Strings 1.3. 🪟 3. Sliding Window (Very Important) 1.4. 🧮 4. Hashing for Strings 1.5. 🔤 5. Pattern Matching Algorithms 1.6. 6. Advanced String Topics
    2. 📝 Must Do String Problems 2.1. 🔹 Level 1 – Easy 2.2. 🔹 Level 2 – Medium 2.3. 🔹 Level 3 – Hard

    🎯 Main Topics Covered

    1. 1 Basics of Strings Foundations
    2. 2 Two Pointers on Strings
    3. 3 Sliding Window Very Important
    4. 4 Hashing for Strings
    5. 5 Pattern Matching Algorithms
    6. img src assetsiconspuzzlesvg relative_url classinline-icon alt 6 Advanced String Topics
    7. Level 1 Easy
    8. Level 2 Medium … and 1 more

    📘 DSA: Strings Learning Roadmap (Beginner → Advanced)

    1. Basics of Strings (Foundations)

    These are must-know before solving problems.

    • Mutable vs Immutable (C++: std::string is mutable)

    • Character arrays vs string class

    • Common operations: length, substring, concatenation, comparison

    • ASCII & Unicode basics

    -> Click here for more details

    🔍 2. Two Pointers on Strings

    Used for many interview problems (palindrome, substring checks).

    Key patterns:

    • Move pointers from left & right

    • Shrink/expand window on conditions

    🪟 3. Sliding Window (Very Important)

    Strings + Sliding Window = 20% of interview questions.

    Understand two types:

    🔸 Fixed Window

    E.g., find anagrams of a pattern.

    🔸 Variable Window

    E.g., longest substring with K distinct characters.

    🧮 4. Hashing for Strings

    Character frequency arrays

    • For lowercase → size 26

    • For ASCII → size 256

    • For Unicode → use hash maps

    Rolling Hash / Rabin-Karp

    • Efficient substring search

    • Used for detecting duplicate substrings, plagiarism, etc.

    Interview problems:

    • Rabin-Karp implementation

    • Longest duplicate substring (binary search + rolling hash)

    🔤 5. Pattern Matching Algorithms

    KMP (Knuth–Morris–Pratt)

    Why important?

    • Used for substring search in O(n + m)

    • LPS array is commonly asked in interviews.

    Z-Algorithm

    • Alternate fast pattern matching

    • Helps in string prefix-based problems

    Trie (String Tree)

    • Useful for autocomplete, prefix search, dictionary problems

    Problems:

    • Word search

    • Longest common prefix

    • Implement Trie

    6. Advanced String Topics

    These help in elite interviews.

    Suffix Array

    • Used for lexicographical ordering of suffixes

    • Applications: substring search, LCP computation

    Suffix Tree / Compressed Trie

    • Extremely fast substring search

    • Rare but high-reward for deep interviews

    Manacher’s Algorithm

    • O(n) longest palindromic substring

    📝 Must Do String Problems

    🔹 Level 1 – Easy

    1. Reverse string

    2. Palindrome check

    3. Count occurrences of characters

    4. Remove duplicates

    5. String compression

    6. Leetcode 412. Fizz Buzz - Solution

    7. Leetcode 14. Longest Common Prefix - Solution

    🔹 Level 2 – Medium

    1. Longest substring without repeating

    2. Longest palindromic substring

    3. Group anagrams

    4. Valid parentheses

    5. Multiply large numbers (string simulation)

    6. Leetcode 271. Encode and Decode Strings{Premium Problem} - My Leetcode Solution link

    7. Leetcode 647. Palindromic Substrings - My Leetcode Solution link

    8. Leetcode 5. Longest Palindromic Substring - My Leetcode Solution link

    🔹 Level 3 – Hard

    1. Minimum window substring

    2. Word break (DP + String)

    3. Regular expression matching (DP)

    4. Wildcard matching

    5. KMP + Z-algorithm applications

    6. Longest duplicate substring (binary search + hash)

    7. Leetcode 647. Palindromic Substrings - My Leetcode Solution link

    8. Leetcode 68. Text Justification - My Leetcode Solution link