DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Master all palindrome problems — basic check with two pointers, Manacher
What Is a Palindrome?
A palindrome reads the same forward and backward.
| "racecar" | palindrome |
| "madam" | palindrome |
| "A man a plan a canal Panama" | palindrome (ignoring spaces/case) |
| "hello" | not a palindrome |
2. Valid Palindrome (Ignore Non-Alphanumeric)
Example
def is_valid_palindrome(s):
"""
Check palindrome ignoring spaces, punctuation, case.
"A man, a plan, a canal: Panama" → True
"""
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_valid_palindrome("A man, a plan, a canal: Panama")) # True
print(is_valid_palindrome("race a car")) # False
3. Longest Palindromic Substring — Expand Around Center
Example
def longest_palindrome_expand(s):
"""
Expand around each center (char or gap between chars).
O(n²) time, O(1) space.
"""
if not s:
return ""
start = end = 0
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1, right - 1 # Return valid palindrome bounds
for i in range(len(s)):
# Odd length palindromes (center at i)
l1, r1 = expand(i, i)
# Even length palindromes (center between i and i+1)
l2, r2 = expand(i, i+1)
if r1 - l1 > end - start:
start, end = l1, r1
if r2 - l2 > end - start:
start, end = l2, r2
return s[start:end+1]
print(longest_palindrome_expand("babad")) # "bab" or "aba"
print(longest_palindrome_expand("cbbd")) # "bb"
print(longest_palindrome_expand("racecar")) # "racecar"
4. Longest Palindromic Substring — Manacher's Algorithm: O(n)
Example
def manacher(s):
"""
Manacher's algorithm — O(n) time, O(n) space.
Finds longest palindromic substring in linear time.
"""
# Transform: "abc" → "#a#b#c#" (handles even/odd uniformly)
t = '#' + '#'.join(s) + '#'
n = len(t)
p = [0] * n # p[i] = radius of palindrome centered at i
center = right = 0 # Rightmost palindrome's center and right boundary
for i in range(n):
mirror = 2 * center - i # Mirror of i around center
if i < right:
p[i] = min(right - i, p[mirror]) # Use mirror info
# Expand around i
while i + p[i] + 1 < n and i - p[i] - 1 >= 0 and t[i + p[i] + 1] == t[i - p[i] - 1]:
p[i] += 1
# Update center and right boundary
if i + p[i] > right:
center, right = i, i + p[i]
# Find max palindrome radius
max_len = max(p)
center_idx = p.index(max_len)
# Convert back to original string indices
start = (center_idx - max_len) // 2
return s[start : start + max_len]
print(manacher("babad")) # "bab"
print(manacher("cbbd")) # "bb"
print(manacher("racecar")) # "racecar"
5. Count All Palindromic Substrings
Example
def count_palindromes(s):
"""Count all palindromic substrings. O(n²)."""
count = 0
def expand(l, r):
nonlocal count
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1
l -= 1
r += 1
for i in range(len(s)):
expand(i, i) # Odd length
expand(i, i+1) # Even length
return count
print(count_palindromes("abc")) # 3 — "a", "b", "c"
print(count_palindromes("aaa")) # 6 — "a","a","a","aa","aa","aaa"
print(count_palindromes("abcba")) # 7
6. Palindrome Partitioning
Example
def min_cuts_palindrome(s):
"""
Minimum cuts to partition s into palindromes.
DP approach. O(n²).
"""
n = len(s)
# is_pal[i][j] = True if s[i..j] is palindrome
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
# dp[i] = min cuts for s[0..i]
dp = list(range(n))
for i in range(1, n):
if is_pal[0][i]:
dp[i] = 0 # Entire s[0..i] is palindrome
else:
for j in range(1, i+1):
if is_pal[j][i]:
dp[i] = min(dp[i], dp[j-1] + 1)
return dp[n-1]
print(min_cuts_palindrome("aab")) # 1 — "a|ab" or "aa|b"
print(min_cuts_palindrome("racecar")) # 0 — whole string is palindrome
7. Palindrome Pairs
Example
def palindrome_pairs(words):
"""
Find all pairs (i,j) where words[i]+words[j] is palindrome.
O(k² × n) brute force, O(n × k²) with hash map.
"""
def is_pal(s): return s == s[::-1]
lookup = {word: i for i, word in enumerate(words)}
result = []
for i, word in enumerate(words):
for k in range(len(word) + 1):
prefix = word[:k]
suffix = word[k:]
# If suffix reversed is in dict and prefix is palindrome
rev_suffix = suffix[::-1]
if is_pal(prefix) and rev_suffix in lookup and lookup[rev_suffix] != i:
result.append([lookup[rev_suffix], i])
# If prefix reversed is in dict and suffix is palindrome (avoid duplicate for k=0)
if k != len(word) and is_pal(suffix):
rev_prefix = prefix[::-1]
if rev_prefix in lookup and lookup[rev_prefix] != i:
result.append([i, lookup[rev_prefix]])
return result
print(palindrome_pairs(["abcd","dcba","lls","s","sssll"]))
# [[0,1],[1,0],[3,2],[2,4]]
Palindrome Pattern Summary
| Problem | Technique | Time | Space |
|---|---|---|---|
| Check palindrome | Two pointers | O(n) | O(1) |
| Longest palindrome | Expand around center | O(n²) | O(1) |
| Longest palindrome (optimal) | Manacher's | O(n) | O(n) |
| Count all palindromes | Expand around center | O(n²) | O(1) |
| Min cuts partition | DP (is_pal + dp) | O(n²) | O(n²) |
Key insight: For palindromes, the "expand around center" technique is the most intuitive and covers both odd and even length palindromes in a clean two-pass loop.
*Next: Anagram Problems*
Continue the lesson path
Study next in this module
01StringsAnagram Problems — Detection, Grouping, and Sliding Window VariationsMaster all anagram-related problems — checking if two strings are anagrams, grouping anagrams together, finding all anagram substrings in a text (sliding window), minimum characters to form anagram, and the frequency array optimization for fixed alphabets.02StringsPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsMaster string pattern searching algorithms — naive O(nm) approach, KMP algorithm with failure function in O(n+m), Rabin-Karp rolling hash approach, Boyer-Moore bad character rule, and when to use each algorithm. Complete implementations with detailed traces.03StringsString Interview Problems — 10 Classic Problems with Complete SolutionsSolve 10 classic string interview problems — reverse words in a string, longest substring without repeating characters, minimum window substring, Roman to integer, integer to string, decode ways, word break, wildcard matching, longest common prefix, and string to integer.04StringsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmMaster string matching and similarity algorithms — Longest Common Subsequence (LCS) with DP, Edit Distance (Levenshtein), Longest Common Substring, Z-algorithm for pattern matching, and their applications in spell checking, DNA analysis, and diff utilities.