Optimizing String Replacement with Sliding Window Approach

Turning a confusing problem into an optimized solution 🚀 Today, I worked on a string problem: Longest Repeating Character Replacement Example: "AABABBA", k = 1 Output = 4 (AAAA, BBBB) Instead of directly jumping to the optimized solution, I explored multiple approaches: 🔹 Brute Force Approach Try all possible substrings Count frequency of characters Check if valid using: length - maxFreq <= k Time Complexity: O(n³) 🔹 Optimized Approach (Sliding Window) Use two pointers (left & right) Expand the window by adding characters Shrink the window when it becomes invalid Reuse previous computations instead of restarting Time Complexity: O(n) Here’s my implementation in JavaScript: function longestSubstringSame(s, k) { let map = {}; let left = 0; let maxFreq = 0; let maxLen = 0; for (let right = 0; right < s.length; right++) { map[s[right]] = (map[s[right]] || 0) + 1; maxFreq = Math.max(maxFreq, map[s[right]]); if ((right - left + 1) - maxFreq > k) { map[s[left]]--; left++; } maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } console.log(longestSubstringSame("AABABBA", 1)); 💡 Key Takeaways: Don’t recompute everything from scratch Sliding Window helps optimize repeated work Understanding the logic behind conditions is crucial Currently improving my skills in Data Structures & Algorithms and building a strong problem-solving mindset. Open to feedback and suggestions! #DSA #JavaScript #ProblemSolving #SoftwareDevelopment #LearningInPublic #AccioJob

To view or add a comment, sign in

Explore content categories