Minimum Window Substring LeetCode Solution

Continuing my 100 Days of DSA journey. Day 70 — LeetCode (Longest Repeating Character Replacement) 1) Longest Repeating Character Replacement – Given a string s and an integer k, return the length of the longest substring that can be obtained by replacing at most k characters so that all characters in the substring are the same. Approach (Sliding Window + Frequency Tracking): a) Use a sliding window with two pointers to maintain a valid substring b) Keep a frequency array to track count of characters in the current window c) Track the count of the most frequent character in the window d) If (window size - max frequency) > k, shrink the window from the left e) This ensures we replace at most k characters f) Update the maximum window length at each step Time Complexity: O(n) Space Complexity: O(1) On to Day 71... #100DaysOfCode #DSA #LeetCode #Cpp #CyclicSort #Algorithms #CodingJourney #ProblemSolving #SoftwareEngineering #InterviewPrep #LearningInPublic #geeksforgeeks #Microsoft #SlidingWindow #Strings #Optimization

🚀 Day 15 of my DSA Grind Sometimes the best way to optimize a Sliding Window problem is to not use a window at all! Today, I tackled a LeetCode Medium that completely changed how I look at substring counting. 🔹 Number of Substrings Containing All Three Characters (LC 1358): The standard approach here is using a left and right pointer to expand and shrink a window until it contains 'a', 'b', and 'c'. But managing those pointers can get messy. The Breakthrough: I scrapped the traditional window and used the "Last Seen" Index array. I simply tracked the exact index where I most recently saw an 'a', a 'b', and a 'c'. The Math: To form a valid substring ending at my current position, I just need to reach back to the minimum of those three indices. Every single index before that minimum is a valid starting point! The Result: By applying the formula count += 1 + min(last_a, last_b, last_c), I reduced the problem to a single, lightning-fast O(N) pass with strict O(1) space. Zero nested loops, zero pointer rewinding! #DataStructures #Algorithms #LeetCode #CPP #ProblemSolving #SoftwareEngineering #PlacementPreparation #Optimization #100DaysOfCode #TechJourney

Continuing my 100 Days of DSA journey. Day 69 — LeetCode (Balanced Binary Tree) Balanced Binary Tree – Given a binary tree, determine if it is height-balanced (i.e., the heights of left and right subtrees of every node differ by no more than 1). Approach (DFS + Height Optimization): a) Use a recursive function to calculate the height of each subtree b) For each node, recursively get the height of left and right subtrees c) If any subtree returns -1, propagate -1 upwards (indicating imbalance) d) Check if the absolute difference between left and right heights is greater than 1 e) If unbalanced, return -1 immediately f) Otherwise, return 1 + max(leftHeight, rightHeight) Time Complexity: O(n) Space Complexity: O(h) (recursion stack) On to Day 70... #100DaysOfCode #DSA #LeetCode #Cpp #Algorithms #CodingJourney #ProblemSolving #SoftwareEngineering #InterviewPrep #LearningInPublic #geeksforgeeks #Microsoft #Greedy #Strings #Optimization

Day 181/365 – DSA Challenge 🌊 Solved Surrounded Regions on LeetCode today. 🔹 Problem: Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. 👉 Replace all 'O' that are completely surrounded with 'X'. 🔹 Approach Used: DFS (Boundary Traversal) 💡 Key Idea: Any 'O' connected to the boundary can never be surrounded. Steps: 1️⃣ Traverse all boundary cells 2️⃣ Run DFS on boundary 'O' → mark them as safe 3️⃣ Traverse entire board: Unvisited 'O' → convert to 'X' Visited 'O' → keep as it is 🔹 Why this works? We avoid checking every region individually. Instead, we eliminate all safe regions first — much more efficient. 🔹 Time Complexity: O(m × n) 🔹 Space Complexity: O(m × n) (visited + recursion stack) 🔹 Concepts Used: DFS, Graph Traversal, Matrix Boundary Logic 🔥 Pattern Recognized: This is similar to problems like Number of Islands — but in reverse thinking (protect instead of count). 💻 Language: C++ Clean logic + strong intuition problem 🚀 #Day181 #365DaysOfCode #DSA #LeetCode #Graphs #DFS #CodingJourney #Cpp

Continuing my 100 Days of DSA journey. Day 71 — LeetCode (Valid Parentheses) Valid Parentheses – Given a string containing just '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if open brackets are closed by the same type and in the correct order. Approach (Stack): a) Use a stack to keep track of opening brackets b) Traverse the string character by character c) If an opening bracket is encountered, push it onto the stack d) If a closing bracket is found: Check if the stack is empty → if yes, return false Otherwise, compare with the top of the stack If it matches the corresponding opening bracket, pop it Else, return false e) At the end, if the stack is empty → valid, otherwise invalid Time Complexity: O(n) Space Complexity: O(n) Key takeaway: Learned how stack helps in handling nested and ordered structures efficiently, especially in problems involving matching pairs. On to Day 72... #100DaysOfCode #DSA #LeetCode #Cpp #CyclicSort #Algorithms #CodingJourney #ProblemSolving #SoftwareEngineering #InterviewPrep #LearningInPublic #geeksforgeeks #Microsoft #Stack #Strings #Parentheses #DataStructures

🚀 𝗬𝗼𝘂 𝗰𝗼𝗺𝗽𝗿𝗲𝘀𝘀 𝟭𝟬 𝗚𝗕, 𝗴𝗲𝘁 𝟯 𝗚𝗕. 𝗬𝗼𝘂 𝗲𝘅𝘁𝗿𝗮𝗰𝘁, 𝗴𝗲𝘁 𝟭𝟬 𝗚𝗕 𝗯𝗮𝗰𝗸. 𝗪𝗵𝗲𝗿𝗲 𝗱𝗶𝗱 𝘁𝗵𝗼𝘀𝗲 𝟳 𝗚𝗕 𝗲𝘃𝗲𝗻 𝗴𝗼? Your file is full of repetition. Way more than you think. A video? Thousands of frames where the background doesn't change. A text file? The word "the" showing up hundreds of times. Code? Same patterns everywhere. The first algorithm, 𝗟𝗭𝟳𝟳, catches this. Instead of storing "the" for the 300th time, it leaves a tiny note - "copy what I wrote 200 bytes ago." That note is 3 bytes. The original was 50. Gone. Then 𝗛𝘂𝗳𝗳𝗺𝗮𝗻 steps in and looks at what's left. It notices some symbols appear constantly, others barely show up. So it gives short codes to the popular ones, longer codes to the rare ones. Like VIP lanes, frequent flyers board faster. Boom. 10 GB becomes 3 GB. Now extraction, The ZIP file secretly carries a codebook inside it. When you extract, it reads that map and works backwards. Huffman restores every symbol. LZ77 follows every pointer and pastes everything back. Byte by byte. Frame by frame. Pixel by pixel. Your original 10 GB, fully restored. Math didn't compress your file. Math just found a smarter way to tell the same story. #SoftwareEngineering #ComputerScience #Programming #TechForEveryone #LearningInPublic #Algorithms #Developer #CodingLife

🚀 Day 39 of solving DSA problems ✅ Problem Solved: Trapping Rain Water Today I solved a classic and very important problem based on arrays and two pointers. 💡 What I learned: Water trapping depends on left max and right max boundaries Har index par water = min(leftMax, rightMax) - height[i] Instead of extra space, we can optimize using Two Pointer approach ⚡ Key Insight: Jis side ki height chhoti hoti hai (left ya right), wahi side decide karti hai ki kitna water store hoga 🧠 Approach: Use two pointers → left & right Track leftMax and rightMax Move the smaller side inward Calculate trapped water on the go ⏱ Complexity: Time: O(n) Space: O(1) ✅ 💻 Result: ✅ Accepted ⚡ Runtime: 0 ms 🔥 Beats 100% Consistency is the key — step by step improvement 🚀 #Day39 #DSA #Arrays #TwoPointers #LeetCode #ProblemSolving #CSharp #CodingJourney #Developer

My experience with Sliding Window — what finally clicked 🔔 When I started solving problems, I used to rely heavily on brute force. Every problem = nested loops 😅 Then I discovered the Sliding Window technique — and it completely changed how I think about arrays and strings. 💡 What is Sliding Window? Instead of recalculating everything again and again, you reuse previous computations by maintaining a "window" over the data. 👉 Think of it like this: You don’t restart… you just slide forward. 🔥 Where is it used? Maximum sum subarray of size K Longest substring without repeating characters Minimum window substring Anagram problems ⚡ Why it’s powerful? Reduces time complexity from O(n²) → O(n) Eliminates unnecessary recomputation Helps you think in terms of optimization 🧠 Basic Pattern: Start with a window (left & right pointer) Expand the window (move right) Shrink when needed (move left) Track your answer 📌 Example Insight: Instead of calculating sum of every subarray separately, just subtract the outgoing element and add the incoming one. That’s it. Simple idea. Massive impact. 💭 My takeaway: DSA is not about memorizing problems… It’s about recognizing patterns. Sliding Window is one of those patterns that shows up everywhere once you truly understand it. . . . . . #DSA #Coding #SoftwareEngineering #ProblemSolving #LeetCode #LearningJourney

🚀 Day 43 of #GeekStreak60 Today’s problem: Painting the Fence (DP) 🎨 Solved a classic Dynamic Programming problem where the goal was to count the number of ways to paint "n" fence posts using "k" colors such that no more than two consecutive posts have the same color. 💡 Learning Takeaway: This problem helped me understand how to break a complex constraint into manageable states. By dividing the problem into two cases — when the last two posts have the same color and when they are different — I was able to build a recurrence relation. It reinforced the idea that many DP problems are about identifying patterns in choices and transitions rather than brute forcing all combinations. ✅ Key Benefits: • Strengthened my understanding of state transitions in DP • Learned how to optimize space by avoiding unnecessary arrays • Improved ability to convert real-world constraints into recurrence relations 📈 Consistency is the real game changer. Showing up daily builds clarity and confidence. 🔥 Current Streak: 43 Days Let’s keep pushing — one problem at a time 💪 #GeekStreak60 #Day43 #DataStructures #Algorithms #DynamicProgramming #CodingJourney #Consistency #PlacementPrep

#Day36 of DSA Journey | https://lnkd.in/gEmw48wF LeetCode 1320 - Minimum Distance to Type a Word Using Two Fingers (Hard) Today’s problem was a true Dynamic Programming challenge — combining geometry + optimization + state management Problem Summary: We are given a string word (uppercase letters A–Z) and a keyboard layout. Each letter has a fixed coordinate We need to type the word using two fingers Movement cost = Manhattan Distance Distance formula: |x1 - x2| + |y1 - y2| Goal: Minimize total typing distance Key Challenges: Two fingers → multiple choices at every step Greedy won’t work Need to explore all possibilities efficiently Core Idea (DP State): At each step, track: Position of finger 1 Position of finger 2 Current index in word State: dp[i][f1][f2] But this is too large Optimization Trick: Instead of tracking both fingers: Fix one finger → optimize the other Use: dp[i][freeFinger] Where: i = current index freeFinger = position of the finger not used in last move Keyboard Mapping: Each letter mapped as: row = Math.floor((charCode - 65) / 6) col = (charCode - 65) % 6