Search Blogs

Showing results for "String Manipulation"

Found 25 results

LeetCode 1807: Evaluate the Bracket Pairs of a String – Java Solution & Explanation

IntroductionLeetCode 1807, Evaluate the Bracket Pairs of a String, is a string-processing problem that combines two common techniques:Using a HashMap for fast key-value lookupTraversing a string while keeping track of whether the current characters belong to a bracket pairThe string contains ordinary characters as well as bracketed keys such as:(name)(age)(city)A separate knowledge list provides the value associated with each known key.For every bracket pair:If the key exists in knowledge, replace the entire pair with its value.If the key is not present, replace the entire pair with ?.For example:s = "(name)is(age)yearsold"with:knowledge = [ ["name", "bob"], ["age", "two"]]becomes:bobistwoyearsoldThe main challenge is identifying exactly which characters belong to a bracketed key while keeping the characters outside brackets unchanged.Question LinkLeetCode 1807 – Evaluate the Bracket Pairs of a StringUnderstanding the ProblemConsider:s = "(name)is(age)yearsold"The bracket pairs are:(name)(age)The text outside the brackets is:isyearsoldSuppose:name → bobage → twoThen the transformation is:(name) → bob(age) → twoSo the final result becomes:bobistwoyearsoldThe characters outside brackets should not be interpreted as keys.For example:s = "(a)(a)aaa"with:a → yesproduces:yesyesaaaThe final aaa remains unchanged because those characters are not inside brackets.ApproachThe solution can be divided into two parts.Store the Knowledge in a HashMapThe knowledge array contains pairs such as:["name", "bob"]["age", "two"]These pairs are stored in a HashMap:HashMap<String, String> mp = new HashMap<>();for(int i = 0; i < knowledge.size(); i++){ mp.put( knowledge.get(i).get(0), knowledge.get(i).get(1) );}This gives direct access to a value using its key.For example:mp.get("name")returns:bobAnd:mp.containsKey("unknown")can be used to determine whether a key exists.Because each key appears at most once in knowledge, there is no need to handle duplicate key definitions.Detecting a Bracketed KeyThe solution uses a boolean variable:boolean bo = false;This represents whether the current position is inside a bracket pair.When the character immediately before the current character is '(':if(i > 0 && s.charAt(i - 1) == '('){ key = ""; bo = true;}the solution starts collecting a new key.For example:(name) ^Once n is reached, the previous character is '(', so the solution begins collecting:nnanamnameWhen ')' is encountered:if(s.charAt(i) == ')'){ bo = false;}the key is complete.The solution can then look it up in the map.Replacing the KeyWhen the closing bracket is found, the code checks whether the collected key exists:if(mp.containsKey(key)){ an += mp.get(key); key = "";}else{ an += "?"; key = "";}If the key is known:(name) → bobIf the key is unknown:(address) → ?This directly follows the problem statement.Keeping Characters Outside BracketsCharacters that are not part of a bracketed key are added directly to the result:if(!bo && (s.charAt(i) != ')' && s.charAt(i) != '(')){ an += s.charAt(i);}This is important because ordinary characters must remain unchanged.For:hi(name)the characters:hiare outside the brackets and are therefore copied directly.The key:nameis evaluated separately.Java SolutionHere is the submitted solution with comments explaining the important parts:class Solution { public String evaluate(String s, List<List<String>> knowledge) { // Store key -> value mappings HashMap<String, String> mp = new HashMap<>(); for(int i = 0; i < knowledge.size(); i++){ mp.put( knowledge.get(i).get(0), knowledge.get(i).get(1) ); } String key = ""; // true when we are currently reading a key boolean bo = false; String an = ""; for(int i = 0; i < s.length(); i++){ // The character after '(' starts a new key if(i > 0 && s.charAt(i - 1) == '('){ key = ""; bo = true; } // ')' means the current key is complete if(s.charAt(i) == ')'){ bo = false; } // Characters outside brackets are copied directly if(!bo && s.charAt(i) != ')' && s.charAt(i) != '('){ an += s.charAt(i); } // Characters inside brackets are collected as the key if(bo){ key += s.charAt(i); } // Evaluate the completed key if(key.length() > 0 && s.charAt(i) == ')'){ if(mp.containsKey(key)){ an += mp.get(key); key = ""; } else{ an += "?"; key = ""; } } } return an; }}Dry RunConsider:s = "(name)is(age)"and:knowledge = [ ["name", "bob"], ["age", "two"]]Initially:an = ""Reading (name)The scanner encounters '('.The next characters are collected as the key:nnanamnameWhen ')' is reached:key = "name"The map contains "name":name → bobSo:an = "bob"Reading isThese characters are outside brackets:isThey are copied directly:an = "bobis"Reading (age)The key is collected:aagageAt the closing bracket:key = "age"The map contains:age → twoSo:an = "bobistwo"The final result is:bobistwoHandling an Unknown KeyConsider:s = "hi(name)"with:knowledge = [["a", "b"]]The map contains only:a → bWhen the scanner reaches:(name)the collected key is:nameBut:mp.containsKey("name")is false.Therefore the entire bracket pair is replaced with:?The result becomes:hi?This is an important part of the problem because unknown keys should not remain in the output.Why a HashMap Works WellThe knowledge list can contain up to 10^5 entries.Searching through the entire list for every bracket pair would be unnecessarily expensive.Instead, the solution converts it into:key → valueusing a HashMap.Then a lookup is expected O(1).This makes the solution efficient even when the knowledge list is large.A Small Implementation ImprovementThe submitted solution uses:String an = "";and repeatedly performs:an += ...Java String objects are immutable, so repeatedly concatenating strings can create many intermediate objects.A StringBuilder is more appropriate when constructing a result character by character.The same approach can therefore be written as:class Solution { public String evaluate(String s, List<List<String>> knowledge) { HashMap<String, String> mp = new HashMap<>(); for(List<String> pair : knowledge){ mp.put(pair.get(0), pair.get(1)); } StringBuilder ans = new StringBuilder(); StringBuilder key = new StringBuilder(); boolean inside = false; for(int i = 0; i < s.length(); i++){ char ch = s.charAt(i); if(ch == '('){ inside = true; key.setLength(0); } else if(ch == ')'){ inside = false; String k = key.toString(); if(mp.containsKey(k)){ ans.append(mp.get(k)); } else{ ans.append('?'); } } else if(inside){ key.append(ch); } else{ ans.append(ch); } } return ans.toString(); }}This version expresses the parsing states more directly:'(' → start keyinside brackets → collect key')' → evaluate keyoutside brackets → copy characterComplexity AnalysisLet:n = length of sk = number of entries in knowledgeBuilding the HashMap requires:Time: O(k)The string is scanned once:Time: O(n)Therefore, the overall expected complexity is:Time Complexity: O(n + k)The HashMap stores all known keys and values.Space Complexity: O(k + n)The O(n) component accounts for the output and temporary string-building structures.Interview TipThis problem is a good example of a state-based string traversal.Instead of trying to manipulate the entire string repeatedly, scan it once and maintain a small amount of state:Outside brackets ↓ '(' ↓Inside bracket → collect key ↓ ')' ↓Look up key ↓Append value / '?' ↓Outside bracketsWhen a string contains delimiters such as:(...)[...]{...}a similar state-based approach can often simplify the implementation.The second important pattern is recognizing when a HashMap is appropriate: whenever many lookups need to be performed using a unique key.ConclusionLeetCode 1807 is primarily a string parsing + HashMap lookup problem.The solution first converts the knowledge list into a key-value map. It then scans the string and distinguishes between characters inside and outside brackets.For every bracketed key:known key → corresponding valueunknown key → ?The important implementation ideas are:Use a HashMap for fast key lookup.Track whether the scanner is inside a bracket pair.Collect characters between '(' and ')'.Preserve characters outside brackets.Return the first available result after processing the complete string.The submitted approach follows this logic correctly. For production-quality Java code, StringBuilder is preferable to repeated String concatenation when constructing the result.

LeetCodeJavaStringHashMapString ManipulationMediumDSA

LeetCode 1980: Find Unique Binary String – Multiple Ways to Generate a Missing Binary Combination

Try the ProblemYou can solve the problem here:https://leetcode.com/problems/find-unique-binary-string/Problem DescriptionYou are given an array nums containing n unique binary strings, where each string has length n.Your task is to return any binary string of length n that does not appear in the array.Important ConditionsEach string consists only of '0' and '1'.Every string in the array is unique.The output must be a binary string of length n.If multiple valid answers exist, any one of them is acceptable.ExamplesExample 1Inputnums = ["01","10"]Output"11"ExplanationPossible binary strings of length 2:00011011Since "01" and "10" are already present, valid answers could be:00 or 11Example 2Inputnums = ["00","01"]Output"11"Another valid output could be:10Example 3Inputnums = ["111","011","001"]Output101Other valid answers include:000010100110Constraintsn == nums.length1 <= n <= 16nums[i].length == nnums[i] consists only of '0' and '1'All strings in nums are uniqueImportant ObservationThe total number of binary strings of length n is:2^nBut the array contains only:n stringsSince 2^n grows very quickly and n ≤ 16, there are many possible binary strings missing from the array. Our goal is simply to construct one of those missing strings.Thinking About the ProblemBefore jumping into coding, it's useful to think about different strategies that could help us generate a binary string that does not appear in the array.Possible Ways to Think About the ProblemWhen approaching this problem, several ideas may come to mind:Generate all possible binary strings of length n and check which one is missing.Store all strings in a HashSet or HashMap and construct a candidate string to verify whether it exists.Manipulate existing strings by flipping bits to create new combinations.Use a mathematical trick that guarantees the new string is different from every string in the list.Each of these approaches leads to a different solution strategy.In this article, we will walk through these approaches and understand how they work.Approach 1: Brute Force – Generate All Binary StringsIdeaThe simplest idea is to generate every possible binary string of length n and check whether it exists in the given array.Since there are:2^n possible binary stringsWe can generate them one by one and return the first string that does not appear in nums.StepsConvert numbers from 0 to (2^n - 1) into binary strings.Pad the binary string with leading zeros so its length becomes n.Check if that string exists in the array.If not, return it.Time ComplexityO(2^n * n)This works because n is at most 16, but it is still not the most elegant approach.Approach 2: HashMap + Bit Flipping (My Approach)IdeaWhile solving this problem, another idea is to store all given binary strings inside a HashMap for quick lookup.Then we can try to construct a new binary string by flipping bits from the existing strings.The intuition is simple:If the current character is '0', change it to '1'.If the current character is '1', change it to '0'.By flipping bits at different positions, we attempt to build a new binary combination.Once the string is constructed, we check whether it already exists in the map.If the generated string does not exist, we return it as our answer.Java Implementation (My Solution)class Solution { public String findDifferentBinaryString(String[] nums) { int len = nums[0].length(); // HashMap to store all given binary strings HashMap<String, Integer> mp = new HashMap<>(); for(int i = 0; i < nums.length; i++){ mp.put(nums[i], i); } int cou = 0; String ans = ""; for(int i = 0; i < nums.length; i++){ if(cou < len){ // Flip the current bit if(nums[i].charAt(cou) == '0'){ ans += '1'; cou++; } else{ ans += '0'; cou++; } }else{ // If generated string does not exist in map if(!mp.containsKey(ans)){ return ans; } // Reset and try building again ans = ""; cou = 0; } } return ans; }}Time ComplexityO(n²)Because we iterate through the array and perform string operations.Space ComplexityO(n)For storing the strings in the HashMap.Approach 3: Cantor’s Diagonalization (Optimal Solution)IdeaA clever mathematical observation allows us to construct a string that must differ from every string in the array.We build a new string such that:The first character differs from the first string.The second character differs from the second string.The third character differs from the third string.And so on.By ensuring that the generated string differs from each string at least at one position, it is guaranteed not to exist in the array.This technique is known as Cantor’s Diagonalization.Java Implementationclass Solution { public String findDifferentBinaryString(String[] nums) { int n = nums.length; StringBuilder result = new StringBuilder(); for(int i = 0; i < n; i++){ // Flip the diagonal bit if(nums[i].charAt(i) == '0'){ result.append('1'); } else{ result.append('0'); } } return result.toString(); }}Time ComplexityO(n)We only traverse the array once.Space ComplexityO(n)For storing the resulting string.Comparison of ApproachesApproachTime ComplexitySpace ComplexityNotesBrute ForceO(2^n * n)O(n)Simple but inefficientHashMap + Bit FlippingO(n²)O(n)Constructive approachCantor DiagonalizationO(n)O(n)Optimal and elegantKey TakeawaysThis problem highlights an interesting concept in algorithm design:Sometimes the best solution is not searching for the answer but constructing one directly.By understanding the structure of the input, we can generate a result that is guaranteed to be unique.ConclusionThe Find Unique Binary String problem can be solved using multiple strategies, ranging from brute force enumeration to clever mathematical construction.While brute force works due to the small constraint (n ≤ 16), more elegant solutions exist. Using hashing or constructive approaches improves efficiency and demonstrates deeper algorithmic thinking.Among all approaches, the Cantor Diagonalization technique provides the most efficient and mathematically guaranteed solution.Understanding problems like this helps strengthen skills in string manipulation, hashing, and constructive algorithms, which are commonly tested in coding interviews.

Binary StringsHashingCantor DiagonalizationLeetCodeMedium

LeetCode 844: Backspace String Compare — Java Solution With All Approaches Explained

IntroductionLeetCode 844 Backspace String Compare is a fantastic problem that shows up frequently in coding interviews. It combines string manipulation, stack simulation, and even has a follow-up that challenges you to solve it in O(1) space — which is what separates a good candidate from a great one.Here is the Link of Question -: LeetCode 844In this article we cover a plain English explanation, real life analogy, 3 Java approaches including the O(1) space two pointer solution, dry runs, complexity analysis, common mistakes, and FAQs.What Is the Problem Really Asking?You are given two strings s and t. Both contain lowercase letters and # characters. Think of # as the backspace key on your keyboard — it deletes the character just before it. If there is nothing to delete, it does nothing.Process both strings through these backspace operations and check if the resulting strings are equal. Return true if equal, false otherwise.Quick Example:s = "ab#c" → # deletes b → becomes "ac"t = "ad#c" → # deletes d → becomes "ac"Both equal "ac" → return true ✅Real Life Analogy — The Keyboard TypoYou are typing a message. You type "ab", realize you made a typo, hit backspace, and type "c". Your friend types "ad", hits backspace, and types "c". Even though you both typed differently, the final message on screen is the same — "ac".That is exactly what this problem is about. Two people typing differently but ending up with the same result.Approach 1: StringBuilder as Stack (Optimal & Clean) ✅The IdeaThis is your own solution and the best O(n) approach. Process each string independently using a StringBuilder as a stack:Letter → append to StringBuilder (push)# → delete last character if StringBuilder is not empty (pop)Then simply compare the two resulting StringBuilders.public boolean backspaceCompare(String s, String t) { return process(s).equals(process(t));}private String process(String str) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (c == '#') { if (sb.length() > 0) { sb.deleteCharAt(sb.length() - 1); } } else { sb.append(c); } } return sb.toString();}Notice how extracting a process() helper method makes the code cleaner and avoids repeating the same loop twice — a great habit to show in interviews!Dry Run — s = "ab##", t = "c#d#"Processing s = "ab##":a → append → "a"b → append → "ab"# → delete last → "a"# → delete last → ""Processing t = "c#d#":c → append → "c"# → delete last → ""d → append → "d"# → delete last → ""Both result in "" → return true ✅Time Complexity: O(n + m) — where n and m are lengths of s and t Space Complexity: O(n + m) — two StringBuilders storing processed stringsApproach 2: Stack Based Solution (Interview Classic)The IdeaSame logic as above but using explicit Stack<Character> objects. Great for explaining your thought process clearly in an interview even though StringBuilder is cleaner.public boolean backspaceCompare(String s, String t) { return processStack(s).equals(processStack(t));}private String processStack(String str) { Stack<Character> st = new Stack<>(); for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (c == '#') { if (!st.empty()) { st.pop(); } } else { st.push(c); } } StringBuilder sb = new StringBuilder(); while (!st.empty()) { sb.append(st.pop()); } return sb.reverse().toString();}Dry Run — s = "a#c", t = "b"Processing s = "a#c":a → push → stack: [a]# → pop → stack: []c → push → stack: [c]Result: "c"Processing t = "b":b → push → stack: [b]Result: "b""c" does not equal "b" → return false ✅Time Complexity: O(n + m) Space Complexity: O(n + m)Approach 3: Two Pointer — O(1) Space (Follow-Up Solution) 🔥This is the follow-up the problem asks about — can you solve it in O(n) time and O(1) space? This means no extra StringBuilder or Stack allowed.The IdeaInstead of building processed strings, traverse both strings from right to left simultaneously. Keep a count of pending backspaces. Skip characters that would be deleted and compare characters that survive.Why right to left? Because # affects characters to its left, so processing from the end lets us know upfront how many characters to skip.public boolean backspaceCompare(String s, String t) { int i = s.length() - 1; int j = t.length() - 1; int skipS = 0, skipT = 0; while (i >= 0 || j >= 0) { // Find next valid character in s while (i >= 0) { if (s.charAt(i) == '#') { skipS++; i--; } else if (skipS > 0) { skipS--; i--; } else { break; } } // Find next valid character in t while (j >= 0) { if (t.charAt(j) == '#') { skipT++; j--; } else if (skipT > 0) { skipT--; j--; } else { break; } } // Compare the valid characters if (i >= 0 && j >= 0) { if (s.charAt(i) != t.charAt(j)) { return false; } } else if (i >= 0 || j >= 0) { return false; // one string still has chars, other doesn't } i--; j--; } return true;}Dry Run — s = "ab#c", t = "ad#c"Starting from the right end of both strings:Round 1:s[3] = 'c' → valid, no skips → stopt[3] = 'c' → valid, no skips → stopCompare 'c' == 'c' ✅ → move both pointers leftRound 2:s[2] = '#' → skipS = 1, move lefts[1] = 'b' → skipS > 0, skipS = 0, move lefts[0] = 'a' → valid, stopt[2] = '#' → skipT = 1, move leftt[1] = 'd' → skipT > 0, skipT = 0, move leftt[0] = 'a' → valid, stopCompare 'a' == 'a' ✅ → move both pointers leftBoth pointers exhausted → return true ✅Time Complexity: O(n + m) — each character visited at most once Space Complexity: O(1) — only pointer and counter variables, no extra storage!Approach ComparisonThe StringBuilder approach is the easiest to write and explain. The Stack approach is slightly more verbose but shows clear intent. The Two Pointer approach is the hardest to code but the most impressive — it solves the follow-up and uses zero extra space.In an interview, start with the StringBuilder solution, explain it clearly, then mention the Two Pointer approach as the O(1) space optimization if asked.How This Fits the Stack Simulation PatternYou have now seen this same pattern across four problems:3174 Clear Digits — digit deletes closest left non-digit 2390 Removing Stars — star deletes closest left non-star 1047 Remove Adjacent Duplicates — character cancels matching top of stack 844 Backspace String Compare — # deletes closest left character, then compare two stringsAll four use the same StringBuilder-as-stack core. The only differences are the trigger character and what you do with the result. This is the power of pattern recognition in DSA.Common Mistakes to AvoidNot handling backspace on empty string When # appears but the StringBuilder is already empty, do nothing. Always guard with sb.length() > 0 before calling deleteCharAt. The problem explicitly states backspace on empty text keeps it empty.Using Stack and forgetting to handle # when stack is empty In the Stack approach, only pop if the stack is not empty. Pushing # onto the stack when it is empty is a common bug that gives wrong answers.In Two Pointer, comparing before both pointers find valid characters Make sure both inner while loops fully complete before comparing. Comparing too early is the most common mistake in the O(1) space solution.FAQs — People Also AskQ1. What is the best approach for LeetCode 844 in Java? For most interviews, the StringBuilder approach is the best — clean, readable, and O(n) time. If the interviewer asks for O(1) space, switch to the Two Pointer approach traversing from right to left.Q2. How does the O(1) space solution work for LeetCode 844? It uses two pointers starting from the end of both strings, keeping a skip counter to track pending backspaces. Characters that would be deleted are skipped, and only surviving characters are compared.Q3. What is the time complexity of LeetCode 844? All three approaches run in O(n + m) time where n and m are the lengths of the two strings. The Two Pointer approach achieves this with O(1) space instead of O(n + m).Q4. Why traverse from right to left in the Two Pointer approach? Because # affects characters to its left. Scanning from the right lets you know upfront how many characters to skip before you reach them, avoiding the need to store anything.Q5. Is LeetCode 844 asked in Google interviews? Yes, it is commonly used as a warmup or screening problem. The follow-up O(1) space solution is what makes it interesting for senior-level interviews.Similar LeetCode Problems to Practice Next1047. Remove All Adjacent Duplicates In String — Easy — same stack pattern2390. Removing Stars From a String — Medium — star as backspace3174. Clear Digits — Easy — digit as backspace1209. Remove All Adjacent Duplicates in String II — Medium — k adjacent duplicates678. Valid Parenthesis String — Medium — stack with wildcardsConclusionLeetCode 844 Backspace String Compare is a well-rounded problem that tests string manipulation, stack simulation, and space optimization all in one. The StringBuilder solution is your go-to for interviews. But always be ready to explain the Two Pointer O(1) space follow-up — that is what shows real depth of understanding.Check out these problems alongside 1047, 2390, and 3174 and you will have the entire stack simulation pattern locked down for any coding interview.

StringStackTwo PointerString Builder

Reverse Only Letters – Two Pointer Strategy Explained (LeetCode 917)

🔗 Problem LinkLeetCode 917 – Reverse Only Letters 👉 https://leetcode.com/problems/reverse-only-letters/IntroductionThis is a very clean two-pointer problem.The challenge is not just reversing a string — it’s reversing only the letters while keeping all non-letter characters in their original positions.This problem strengthens:Two pointer techniqueCharacter validation logicIn-place string manipulationLet’s break it down.📌 Problem UnderstandingYou are given a string s.Rules:All non-English letters must remain at the same index.Only English letters (uppercase or lowercase) should be reversed.Return the modified string.Example 1Input: "ab-cd"Output: "dc-ba"Only letters are reversed. Hyphen stays at same position.Example 2Input: "a-bC-dEf-ghIj"Output: "j-Ih-gfE-dCba"Example 3Input: "Test1ng-Leet=code-Q!"Output: "Qedo1ct-eeLg=ntse-T!"Notice:Numbers, -, =, ! stay fixed.Only letters move.🧠 IntuitionThe first thought might be:Extract all lettersReverse themPut them backBut that would require extra space.Instead, we can solve this efficiently using Two Pointers.🚀 Two Pointer ApproachWe use:i → starting from leftj → starting from rightSteps:Convert string into char array.Move i forward until it points to a letter.Move j backward until it points to a letter.Swap letters.Continue until i < j.💻 Your Codeclass Solution { public String reverseOnlyLetters(String s) { int i = 0; int j = s.length() - 1; char arr[] = s.toCharArray(); while(i < j){ boolean l = ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') || ('a' <= s.charAt(i) && s.charAt(i) <= 'z'); boolean r = ('A' <= s.charAt(j) && s.charAt(j) <= 'Z') || ('a' <= s.charAt(j) && s.charAt(j) <= 'z'); if(l && r){ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; }else if(l){ j--; }else if(r){ i++; }else{ i++; j--; } } return new String(arr); }}🔍 Step-by-Step Explanation1️⃣ Convert to Character Arraychar arr[] = s.toCharArray();Strings are immutable in Java. So we convert to char array to modify it.2️⃣ Initialize Two Pointersint i = 0;int j = s.length() - 1;We start from both ends.3️⃣ Check If Characters Are Lettersboolean l = ('A' <= s.charAt(i) && s.charAt(i) <= 'Z') || ('a' <= s.charAt(i) && s.charAt(i) <= 'z');You manually check ASCII ranges for uppercase and lowercase letters.Same logic for r.4️⃣ Swap When Both Are Lettersif(l && r){ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--;}Only swap letters.5️⃣ Move Pointers When One Is Not LetterIf left is letter but right is not → move jIf right is letter but left is not → move iIf both are not letters → move bothThis ensures:Non-letter characters remain in their positions.🎯 Why This WorksWe never move non-letter characters.We only swap valid letters.Since we use two pointers:Time complexity stays linear.No extra array needed for letters.⏱ Complexity AnalysisTime Complexity: O(n)Each character is visited at most once.Space Complexity: O(n)Because we convert string to char array.(If considering output string creation, still O(n))🔥 Cleaner OptimizationInstead of manually checking ASCII ranges, Java provides:Character.isLetter(c)Cleaner version:class Solution { public String reverseOnlyLetters(String s) { int i = 0, j = s.length() - 1; char[] arr = s.toCharArray(); while(i < j){ if(!Character.isLetter(arr[i])){ i++; }else if(!Character.isLetter(arr[j])){ j--; }else{ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } return new String(arr); }}Much cleaner and readable.🏁 Final ThoughtsThis problem teaches:Two pointer patternIn-place string reversalCharacter validation logicClean pointer movement strategyIt’s a simple but powerful pattern that appears often in interviews.If you master this, you can easily solve:Reverse Vowels of a StringValid PalindromeReverse String IIPalindrome with One Removal

Two PointersString ManipulationLeetCodeEasy

All Subsequences of a String (Power Set) | Recursion & Backtracking Java Solution

IntroductionThe Power Set problem for strings is a classic question in recursion and backtracking, frequently asked in coding interviews and platforms like GeeksforGeeks.In this problem, instead of numbers, we deal with strings and generate all possible subsequences (not substrings). This makes it slightly more interesting and practical for real-world applications like pattern matching, text processing, and combinatorics.In this article, we will cover:Intuition behind subsequencesRecursive (backtracking) approachSorting for lexicographical orderAlternative approachesComplexity analysisProblem StatementGiven a string s of length n, generate all non-empty subsequences of the string.RequirementsReturn only non-empty subsequencesOutput must be in lexicographically sorted orderExamplesExample 1Input:s = "abc"Output:a ab abc ac b bc cExample 2Input:s = "aa"Output:a a aaSubsequence vs Substring (Important)Substring: Continuous charactersSubsequence: Characters can be skippedExample for "abc":Subsequences → a, b, c, ab, ac, bc, abcKey InsightFor every character, we have two choices:Include it OR Exclude itSo total subsequences:2^nWe generate all and then remove the empty string.Approach 1: Recursion (Backtracking)IntuitionAt each index:Skip the characterInclude the characterBuild all combinations recursivelyJava Code (With Explanation)import java.util.*;class Solution { // List to store all subsequences List<String> a = new ArrayList<>(); void sub(String s, int ind, String curr) { // Base case: reached end of string if (ind == s.length()) { a.add(curr); // add current subsequence return; } // Choice 1: Exclude current character sub(s, ind + 1, curr); // Choice 2: Include current character sub(s, ind + 1, curr + s.charAt(ind)); } public List<String> AllPossibleStrings(String s) { // Start recursion sub(s, 0, ""); // Remove empty string (not allowed) a.remove(""); // Sort lexicographically Collections.sort(a); return a; }}Step-by-Step Dry Run (s = "abc")Start: ""→ Exclude 'a' → "" → Exclude 'b' → "" → Exclude 'c' → "" → Include 'c' → "c" → Include 'b' → "b" → Exclude 'c' → "b" → Include 'c' → "bc"→ Include 'a' → "a" → Exclude 'b' → "a" → Exclude 'c' → "a" → Include 'c' → "ac" → Include 'b' → "ab" → Exclude 'c' → "ab" → Include 'c' → "abc"Final Output (After Sorting)a ab abc ac b bc cApproach 2: Bit ManipulationIntuitionEach subsequence can be represented using binary numbers:0 → exclude1 → includeCodeimport java.util.*;class Solution { public List<String> AllPossibleStrings(String s) { List<String> result = new ArrayList<>(); int n = s.length(); int total = 1 << n; // 2^n for (int i = 1; i < total; i++) { // start from 1 to avoid empty StringBuilder sb = new StringBuilder(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { sb.append(s.charAt(j)); } } result.add(sb.toString()); } Collections.sort(result); return result; }}Approach 3: Iterative (Expanding List)IdeaStart with empty listFor each character:Add it to all existing subsequencesCodeimport java.util.*;class Solution { public List<String> AllPossibleStrings(String s) { List<String> result = new ArrayList<>(); result.add(""); for (char ch : s.toCharArray()) { int size = result.size(); for (int i = 0; i < size; i++) { result.add(result.get(i) + ch); } } result.remove(""); Collections.sort(result); return result; }}Complexity AnalysisTime Complexity: O(n × 2ⁿ)Space Complexity: O(n × 2ⁿ)Why?Total subsequences = 2ⁿEach subsequence takes O(n) to buildWhy Sorting is RequiredThe recursion generates subsequences in random order, so we sort them:Collections.sort(result);This ensures lexicographical order as required.Key TakeawaysThis is a power set problem for stringsEach character → 2 choicesRecursion = most intuitive approachBit manipulation = most optimized thinkingAlways remove empty string if requiredCommon Interview VariationsSubsets of arrayPermutations of stringCombination sumSubsequence with conditionsConclusionThe Power Set problem is a fundamental building block in recursion and combinatorics. Once you understand the include/exclude pattern, you can solve a wide range of problems efficiently.Mastering this will significantly improve your ability to tackle backtracking and decision tree problems.Frequently Asked Questions (FAQs)1. Why is the empty string removed?Because the problem requires only non-empty subsequences.2. Why is time complexity O(n × 2ⁿ)?Because there are 2ⁿ subsequences and each takes O(n) time to construct.3. Which approach is best?Recursion → best for understandingBit manipulation → best for optimization

GeeksforGeeksRecursionJavaBacktrackingMedium

LeetCode 2390: Removing Stars From a String — Java Solution With All Approaches Explained

Introduction: What Is LeetCode 2390 Removing Stars From a String?If you are preparing for coding interviews at companies like Google, Amazon, or Microsoft, LeetCode 2390 Removing Stars From a String is a must-solve problem. It tests your understanding of the stack data structure and string manipulation — two of the most frequently tested topics in technical interviews.In this article, we will cover:What the problem is asking in plain English3 different Java approaches (Brute Force, Stack, StringBuilder)Step-by-step dry run with examplesTime and space complexity for each approachCommon mistakes to avoidFAQs that appear in Google's People Also AskLet's dive in!Problem Statement SummaryYou are given a string s containing lowercase letters and stars *. In one operation:Choose any * in the stringRemove the * itself AND the closest non-star character to its leftRepeat until all stars are removed and return the final string.Example:Input: s = "leet**cod*e"Output: "lecoe"Real Life Analogy — Think of It as a Backspace KeyImagine you are typing on a keyboard. Every * acts as your backspace key — it deletes itself and the character just before it.You type "leet" and press backspace twice:Backspace 1 → deletes t → "lee"Backspace 2 → deletes e → "le"That is exactly what this problem simulates! Once you see it this way, the solution becomes very obvious.Approach 1: Brute Force Simulation (Beginner Friendly)IdeaDirectly simulate the process the problem describes:Scan the string from left to rightFind the first *Remove it and the character just before itRepeat until no stars remainJava Codepublic String removeStars(String s) {StringBuilder sb = new StringBuilder(s);int i = 0;while (i < sb.length()) {if (sb.charAt(i) == '*') {sb.deleteCharAt(i); // remove the starif (i > 0) {sb.deleteCharAt(i - 1); // remove closest left characteri--;}} else {i++;}}return sb.toString();}Time and Space ComplexityComplexityValueReasonTimeO(n²)Each deletion shifts all remaining charactersSpaceO(n)StringBuilder storage⚠️ Important WarningThis problem has n up to 100,000. Brute force will get Time Limit Exceeded (TLE) on LeetCode. Use this only to understand the concept, never in production or interviews.Approach 2: Stack Based Solution (Interview Favorite)IdeaA stack is the perfect data structure here because:We always remove the most recently added letter when a * appearsThat is the definition of Last In First Out (LIFO) — exactly what a stack doesAlgorithm:Letter → push onto stack* → pop from stack (removes closest left character)At the end, build result from stack contentsJava Codepublic String removeStars(String s) {Stack<Character> st = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '*') {if (!st.empty()) {st.pop();}} else {st.push(c);}}StringBuilder sb = new StringBuilder();while (!st.empty()) {sb.append(st.pop());}return sb.reverse().toString();}Step-by-Step Dry Run — "leet**cod*e"StepCharacterActionStack State1lpush[l]2epush[l,e]3epush[l,e,e]4tpush[l,e,e,t]5*pop t[l,e,e]6*pop e[l,e]7cpush[l,e,c]8opush[l,e,c,o]9dpush[l,e,c,o,d]10*pop d[l,e,c,o]11epush[l,e,c,o,e]✅ Final Answer: "lecoe"Time and Space ComplexityComplexityValueReasonTimeO(n)Single pass through the stringSpaceO(n)Stack holds up to n charactersApproach 3: StringBuilder as Stack (Optimal Solution) ✅IdeaThis is the best and most optimized approach. A StringBuilder can act as a stack:append(c) → works like pushdeleteCharAt(sb.length() - 1) → works like popNo reverse needed at the end unlike the Stack approachJava Codepublic String removeStars(String s) {StringBuilder sb = new StringBuilder();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '*') {if (sb.length() > 0) {sb.deleteCharAt(sb.length() - 1);}} else {sb.append(c);}}return sb.toString();}Step-by-Step Dry Run — "erase*****"StepCharacterActionStringBuilder1eappend"e"2rappend"er"3aappend"era"4sappend"eras"5eappend"erase"6*delete last"eras"7*delete last"era"8*delete last"er"9*delete last"e"10*delete last""✅ Final Answer: ""Why StringBuilder Beats Stack in JavaFactorStack<Character>StringBuilderMemoryBoxes char → Character objectWorks on primitives directlyReverse neededYesNoCode lengthMore verboseCleaner and shorterPerformanceSlightly slowerFasterTime and Space ComplexityComplexityValueReasonTimeO(n)One pass, each character processed onceSpaceO(n)StringBuilder storageAll Approaches Comparison TableApproachTimeSpacePasses LeetCode?Best ForBrute ForceO(n²)O(n)❌ TLEUnderstanding conceptStackO(n)O(n)✅ YesInterview explanationStringBuilderO(n)O(n)✅ YesBest solutionHow This Relates to LeetCode 3174 Clear DigitsIf you have already solved LeetCode 3174 Clear Digits, you will notice this problem is nearly identical:Feature3174 Clear Digits2390 Removing StarsTriggerDigit 0-9Star *RemovesClosest left non-digitClosest left non-starDifficultyEasyMediumBest approachStringBuilderStringBuilderThe exact same solution pattern works for both. This is why learning patterns matters more than memorizing individual solutions!Common Mistakes to Avoid1. Not checking sb.length() > 0 before deleting Even though the problem guarantees valid input, always add this guard. It shows clean, defensive coding in interviews.2. Forgetting to reverse when using Stack Stack gives you characters in reverse order. If you forget .reverse(), your answer will be backwards.3. Using Brute Force for large inputs With n up to 100,000, O(n²) will time out. Always use the O(n) approach.FAQs — People Also AskQ1. What data structure is best for LeetCode 2390? A Stack or StringBuilder used as a stack is the best data structure. Both give O(n) time complexity. StringBuilder is slightly more optimal in Java because it avoids object boxing overhead.Q2. Why does a star remove the closest left character? Because the problem defines it that way — think of * as a backspace key on a keyboard. It always deletes the character immediately before the cursor position.Q3. What is the time complexity of LeetCode 2390? The optimal solution runs in O(n) time and O(n) space, where n is the length of the input string.Q4. Is LeetCode 2390 asked in Google interviews? Yes, this type of stack simulation problem is commonly asked at Google, Amazon, Microsoft, and Meta interviews as it tests understanding of LIFO operations and string manipulation.Q5. What is the difference between LeetCode 2390 and LeetCode 844? Both use the same backspace simulation pattern. In 844 Backspace String Compare, # is the backspace character and you compare two strings. In 2390, * is the backspace and you return the final string.Similar LeetCode Problems to Practice NextProblemDifficultyPattern844. Backspace String CompareEasyStack simulation1047. Remove All Adjacent Duplicates In StringEasyStack simulation3174. Clear DigitsEasyStack simulation20. Valid ParenthesesEasyClassic stack735. Asteroid CollisionMediumStack simulationConclusionLeetCode 2390 Removing Stars From a String is a classic stack simulation problem that every developer preparing for coding interviews should master. The key insight is recognizing that * behaves exactly like a backspace key, which makes a stack or StringBuilder the perfect tool.Quick Recap:Brute force works conceptually but TLEs on large inputsStack solution is clean and great for explaining in interviewsStringBuilder solution is the most optimal in Java — no boxing, no reversal

StringStackMediumLeetCode

LeetCode 784 Letter Case Permutation | Recursion & Backtracking Java Solution

IntroductionThe Letter Case Permutation problem is a classic example of recursion and backtracking, often asked in coding interviews and frequently searched by learners preparing for platforms like LeetCode.This problem helps in understanding:Decision-making at each stepRecursive branchingString manipulationIn this article, we’ll break down the intuition, visualize the decision process using your decision tree, and implement an efficient Java solution.🔗 Problem LinkLeetCode: Letter Case PermutationProblem StatementGiven a string s, you can transform each alphabet character into:LowercaseUppercaseDigits remain unchanged.👉 Return all possible strings formed by these transformations.ExamplesExample 1Input:s = "a1b2"Output:["a1b2","a1B2","A1b2","A1B2"]Example 2Input:s = "3z4"Output:["3z4","3Z4"]Key InsightAt each character:If it's a digit → only one choiceIf it's a letter → two choices:lowercase OR uppercaseSo total combinations:2^(number of letters)Intuition (Using Your Decision Tree)For input: "a1b2"Start from index 0: "" / \ "a" "A" | | "a1" "A1" / \ / \ "a1b" "a1B" "A1b" "A1B" | | | | "a1b2" "a1B2" "A1b2" "A1B2"Understanding the TreeAt 'a' → branch into 'a' and 'A''1' → no branching (digit)'b' → again branching'2' → no branching📌 Leaf nodes = final answersApproach: Recursion + BacktrackingIdeaTraverse the string character by characterIf digit → move forwardIf letter → branch into:lowercaseuppercaseJava Codeimport java.util.*;class Solution { // List to store all results List<String> lis = new ArrayList<>(); public void solve(String s, int ind, String ans) { // Base case: reached end of string if (ind == s.length()) { lis.add(ans); // store generated string return; } char ch = s.charAt(ind); // If character is a digit → only one option if (ch >= '0' && ch <= '9') { solve(s, ind + 1, ans + ch); } else { // Choice 1: convert to lowercase solve(s, ind + 1, ans + Character.toLowerCase(ch)); // Choice 2: convert to uppercase solve(s, ind + 1, ans + Character.toUpperCase(ch)); } } public List<String> letterCasePermutation(String s) { solve(s, 0, ""); // start recursion return lis; }}Step-by-Step ExecutionFor "a1b2":Start → ""'a' → "a", "A"'1' → "a1", "A1"'b' → "a1b", "a1B", "A1b", "A1B"'2' → final stringsComplexity AnalysisTime Complexity: O(2^n)(n = number of letters)Space Complexity: O(2^n)(for storing results)Why This Approach WorksRecursion explores all possibilitiesEach letter creates a branching pointDigits pass through unchangedBacktracking ensures all combinations are generatedKey TakeawaysThis is a binary decision recursion problemLetters → 2 choicesDigits → 1 choiceDecision tree directly maps to recursionPattern similar to:SubsetsPermutations with conditionsWhen This Problem Is AskedCommon in:Coding interviewsRecursion/backtracking roundsString manipulation problemsConclusionThe Letter Case Permutation problem is a perfect example of how recursion can be used to explore all possible combinations efficiently.Once the decision tree is clear, the implementation becomes straightforward. This pattern is widely used in many advanced problems, making it essential to master.Frequently Asked Questions (FAQs)1. Why don’t digits create branches?Because they have only one valid form.2. What is the main concept used?Recursion with decision-making (backtracking).3. Can this be solved iteratively?Yes, using BFS or iterative expansion, but recursion is more intuitive.

LeetCodeMediumJavaRecursion

LeetCode 2086: Minimum Number of Food Buckets to Feed the Hamsters – Java Greedy Solution

IntroductionSome greedy problems look simple at first, but the order in which decisions are made can make a big difference.In this problem, each 'H' represents a hamster and each '.' represents an empty position where a food bucket can be placed. Every hamster needs at least one bucket immediately to its left or right.The goal is to feed every hamster using the minimum number of buckets.The key observation is:When a hamster needs a bucket, placing it on the right side is generally the best choice because that bucket may also help a future hamster.This creates a natural left-to-right greedy strategy.Question LinkLeetCode 2086 – Minimum Number of Food Buckets to Feed the HamstersUnderstanding the ProblemConsider:H.HThe hamster on the left and the hamster on the right can both use the same bucket:H 0 HSo only one bucket is required.But consider:H..HOne bucket cannot feed both hamsters because they are two positions apart:H 0 . HThe second hamster still has no adjacent bucket.Therefore, two buckets are necessary:H 0 0 HThere is also an impossible case:HHHThe middle hamster has no empty position next to it, so there is no way to feed it.Greedy ApproachThe string is scanned from left to right.Whenever a hamster 'H' is encountered:If it already has a bucket on either side, nothing needs to be done.Otherwise, if the right position is empty, place a bucket there.If the right position cannot be used, try the left position.If both neighboring positions contain hamsters, feeding that hamster is impossible, so return -1.A character '0' is used to represent a bucket that has already been placed.Why prefer the right side?Suppose the current hamster is:H . HPlacing the bucket on the right side of the current hamster gives:H 0 HThe next hamster is also fed by the same bucket.Therefore, choosing the right side can allow one bucket to serve two consecutive hamsters.Java SolutionThe following implementation directly simulates the placement of buckets inside a character array.class Solution { public int minimumBuckets(String hams) { // Special case: a single empty position needs no bucket. if (hams.length() == 1 && hams.charAt(0) == '.') { return 0; } // A single hamster has no neighboring position. if (hams.length() == 1 && hams.charAt(0) == 'H') { return -1; } // Convert the string into a character array // so bucket placements can be marked. char[] ham = hams.toCharArray(); // Number of buckets placed. int am = 0; // Process every position from left to right. for (int i = 0; i < ham.length; i++) { if (ham[i] == 'H') { // Case where the hamster has both left and right neighbors. if (i > 0 && i < ham.length - 1) { // If a bucket is already nearby, // this hamster is already fed. if (ham[i + 1] == '0' || ham[i - 1] == '0') { continue; } // Both neighbors are hamsters, // so no bucket can be placed for this hamster. if (ham[i + 1] == 'H' && ham[i - 1] == 'H') { return -1; } // Prefer placing the bucket on the right. // This may also feed the next hamster. if (ham[i + 1] == '.') { ham[i + 1] = '0'; am++; } // If the right side is unavailable, // place the bucket on the left. else { if (ham[i - 1] == '.') { ham[i - 1] = '0'; am++; } } } else { // Hamster at the first position. if (i == 0) { // Only the right side is available. if (ham[i + 1] == '.') { ham[i + 1] = '0'; am++; } else { // Another hamster means this hamster // cannot be fed. if (ham[i + 1] == 'H') { return -1; } } } else { // Hamster at the last position. if (i == ham.length - 1) { if (ham[i] == 'H') { // Only the left side is available. if (ham[i - 1] == '.') { ham[i - 1] = '0'; am++; } else { // Another hamster means impossible. if (ham[i - 1] == 'H') { return -1; } } } } } } } } return am; }}Dry RunConsider:hamsters = ".H.H."Initial array:. H . H .First hamsterThe hamster at index 1 has:index 0 → .index 2 → .The algorithm prefers the right side.Place a bucket at index 2:. H 0 H .Bucket count:1Second hamsterThe hamster at index 3 checks its neighbors:index 2 → 0index 4 → .A bucket already exists at index 2, so this hamster is already fed.No new bucket is required.Final arrangement:. H 0 H .Answer:1Another ExampleConsider:H..HInitially:H . . HThe first hamster places a bucket on its right:H 0 . HThe second hamster does not have a bucket next to it, so it places one on its left:H 0 0 HTotal:2Impossible CaseConsider:.HHH.The middle hamster has hamsters on both sides:. H H H . ↑There is no empty adjacent position for it.Even if buckets are placed at both ends:0 H H H 0the middle hamster still cannot reach a bucket.Therefore:-1Complexity AnalysisLet n be the length of the string.Time ComplexityThe array is traversed once:O(n)Each position is processed a constant number of times.Space ComplexityThe string is converted into a character array:O(n)Apart from that, only a constant amount of extra variables is used.Why This Greedy Strategy WorksThe important decision is what to do when a hamster has no bucket nearby.If the right position is empty, placing the bucket there is preferred because:H . Hbecomes:H 0 HOne bucket now handles two hamsters.If the bucket were instead placed on the left, the next hamster might still require another bucket.Therefore, processing from left to right and preferring the right side makes each bucket as useful as possible.The already placed buckets are marked as '0', allowing later hamsters to immediately recognize that they are already fed.A Useful Pattern to RememberThis problem is a good example of local greedy decisions producing a globally optimal result.When a position needs a resource and there are multiple valid choices, ask:Which choice can also help future elements?Here, the answer is usually the right-side bucket.This same type of reasoning appears frequently in greedy problems involving:IntervalsArraysString simulationsSchedulingResource placementCovering neighboring elementsInterview TipFor an interview, the most important part is not memorizing the implementation.The core reasoning should be clear:Hamster already fed → skipRight side empty → place bucket thereOtherwise left side empty → place bucket thereBoth sides are hamsters → impossibleThe right-side preference is the key optimization because a bucket can potentially serve the next hamster as well.ConclusionLeetCode 2086 is a compact greedy problem where careful local decisions are enough to obtain the minimum number of buckets.The main idea is to scan from left to right, avoid placing unnecessary buckets, and whenever a bucket is required, prefer the right side whenever possible. Existing buckets are marked directly in the array so that later hamsters can reuse them.The resulting solution runs in O(n) time, making it easily suitable for the constraint of up to 10⁵ positions.

LeetCodeJavaGreedyStringSimulationArraysString ManipulationMedium

Minimum Changes to Make Alternating Binary String – LeetCode 1758 Explained

Try This QuestionBefore reading the solution, try solving the problem yourself on LeetCode:👉 https://leetcode.com/problems/minimum-changes-to-make-alternating-binary-string/Problem StatementYou are given a binary string s consisting only of characters '0' and '1'.In one operation, you can change any '0' to '1' or '1' to '0'.A string is called alternating if no two adjacent characters are the same.Example of Alternating Strings01010101011010Example of Non-Alternating Strings0001001111101Your task is to return the minimum number of operations required to make the string alternating.Example WalkthroughExample 1Inputs = "0100"Possible fix:0101Only the last character needs to change, so the answer is:Output1Example 2Inputs = "10"The string is already alternating.Output0Example 3Inputs = "1111"Possible alternating strings:01011010Minimum operations needed = 2Output2Key ObservationAn alternating binary string can only have two possible patterns:Pattern 10101010101...Pattern 21010101010...So instead of trying many combinations, we only need to check:1️⃣ How many changes are required to convert s → "010101..."2️⃣ How many changes are required to convert s → "101010..."Then we return the minimum of the two.ApproachStep 1Generate two possible alternating strings:s1 = "010101..."s2 = "101010..."Both will be of the same length as the input string.Step 2Compare the original string with both patterns.Count mismatches.For example:s = 0100s1 = 0101Mismatch count = 1Step 3Repeat for the second pattern.Finally return:min(mismatch1, mismatch2)Intuition Behind the SolutionInstead of flipping characters randomly, we compare the string with the two valid alternating possibilities.Why only two?Because:Alternating strings must start with either 0 or 1After that, the pattern is fixed.So we simply compute which pattern requires fewer changes.This makes the solution efficient and simple.Java Implementationclass Solution { public int minOperations(String s) { int co1 = 0; int co2 = 0; String s1 = ""; String s2 = ""; for(int i = 0; i < s.length(); i++){ if(i % 2 == 0){ s1 += "0"; } else { s1 += "1"; } } for(int i = 0; i < s.length(); i++){ if(i % 2 == 0){ s2 += "1"; } else { s2 += "0"; } } for(int i = 0; i < s.length(); i++){ if(s.charAt(i) != s1.charAt(i)){ co1++; } } for(int i = 0; i < s.length(); i++){ if(s.charAt(i) != s2.charAt(i)){ co2++; } } return Math.min(co1, co2); }}Complexity AnalysisTime ComplexityO(n)We iterate through the string a few times.Space ComplexityO(n)Because we create two extra strings of size n.Optimized Approach (Better Interview Answer)We can avoid creating extra strings and calculate mismatches directly.Optimized Java Codeclass Solution { public int minOperations(String s) { int pattern1 = 0; int pattern2 = 0; for(int i = 0; i < s.length(); i++){ char expected1 = (i % 2 == 0) ? '0' : '1'; char expected2 = (i % 2 == 0) ? '1' : '0'; if(s.charAt(i) != expected1) pattern1++; if(s.charAt(i) != expected2) pattern2++; } return Math.min(pattern1, pattern2); }}Space Complexity NowO(1)No extra strings required.Why This Problem Is ImportantThis problem teaches important interview concepts:✔ Pattern observation✔ Greedy thinking✔ String manipulation✔ Optimization techniquesMany companies ask similar pattern-based string problems.Final ThoughtsThe trick in this problem is realizing that only two alternating patterns exist. Once you identify that, the problem becomes straightforward.Instead of trying multiple modifications, you simply compare and count mismatches.This leads to a clean and efficient O(n) solution.If you are preparing for coding interviews, practicing problems like this will improve your pattern recognition skills, which is a key skill for solving medium and hard problems later.Happy Coding 🚀

LeetCodeBinary StringGreedy AlgorithmJavaEasy

LeetCode 3120: Count the Number of Special Characters I – Java HashSet Solution Explained

IntroductionLeetCode 3120 – Count the Number of Special Characters I is a beginner-friendly string and hashing problem.This problem focuses on:Character manipulationUppercase and lowercase conversionHashSet usageString traversalBasic optimization techniquesIt is a good interview problem for testing:Understanding of ASCII charactersJava Character methodsSet operationsProblem-solving logicProblem Link🔗 https://leetcode.com/problems/count-the-number-of-special-characters-i/Problem StatementYou are given a string:wordA character is called:specialif it appears in both:LowercaseUppercaseReturn:Total number of special charactersExample 1Inputword = "aaAbcBC"Output3ExplanationCharacters:'a' and 'A''b' and 'B''c' and 'C'All appear in both cases.So answer is:3Example 2Inputword = "abc"Output:0No uppercase letters exist.Example 3Inputword = "abBCab"Output:1Only:'b' and 'B'appear in both forms.IntuitionWe need to check:For every lowercase character:Does its uppercase version exist?Using HashSet makes lookup very fast.Brute Force ApproachIdeaFor every character:Traverse entire stringSearch for uppercase/lowercase pairCount valid matchesBrute Force ComplexityTime ComplexityO(N²)because nested traversal is required.Space ComplexityO(1)Optimized HashSet ApproachIdeaUse two sets:One for lowercase lettersOne for uppercase lettersThen check matching pairs.Java Solutionclass Solution {public int numberOfSpecialChars(String word) {HashSet<Character> lower = new HashSet<>();HashSet<Character> upper = new HashSet<>();for(int i = 0; i < word.length(); i++) {if(word.charAt(i) >= 'a' && word.charAt(i) <= 'z') {lower.add(word.charAt(i));}else {upper.add(word.charAt(i));}}int ans = 0;for(int i = 0; i < word.length(); i++) {char up = Character.toUpperCase(word.charAt(i));if(lower.contains(word.charAt(i)) && upper.contains(up)) {ans++;lower.remove(word.charAt(i));upper.remove(up);}}return ans;}}Cleaner Optimized Versionclass Solution {public int numberOfSpecialChars(String word) {HashSet<Character> lower = new HashSet<>();HashSet<Character> upper = new HashSet<>();for(char ch : word.toCharArray()) {if(Character.isLowerCase(ch)) {lower.add(ch);}else {upper.add(ch);}}int count = 0;for(char ch : lower) {if(upper.contains(Character.toUpperCase(ch))) {count++;}}return count;}}Why This WorksWe separate:Lowercase charactersUppercase charactersThen for every lowercase letter:We check whether uppercase version exists.HashSet lookup works in:O(1)average time.Dry RunInputword = "aaAbcBC"Step 1Lowercase set:[a, b, c]Uppercase set:[A, B, C]Step 2Check:'a' → 'A' exists'b' → 'B' exists'c' → 'C' existsCount becomes:3Final Answer3Time Complexity AnalysisOptimized HashSet SolutionTime ComplexityO(N)because string traversal happens only once.Space ComplexityO(1)Maximum alphabet size is fixed:26 lowercase + 26 uppercaseBrute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(1)HashSet ApproachO(N)O(1)Interview ExplanationIn interviews, explain:We use two HashSets to separately store lowercase and uppercase letters. Then we check whether a lowercase character has its uppercase counterpart.This demonstrates:Efficient lookup usageHashing knowledgeCharacter manipulation skillsCommon Mistakes1. Double Counting CharactersWithout removing counted characters:same letter may be counted multiple times2. Forgetting Case ConversionAlways convert:Character.toUpperCase(ch)before comparison.3. Using Nested Loops UnnecessarilyHashSet reduces lookup complexity significantly.FAQsQ1. Why use HashSet?Because lookup operations are very fast.Q2. Can this be solved without extra space?Yes.Using arrays of size 26 is also possible.Q3. Why remove characters after counting?To avoid duplicate counting.Q4. Is this problem important for interviews?Yes.It tests:String handlingCharacter conversionHashSet usageOptimization thinkingRelated ProblemsPractice these next:Valid AnagramFirst Unique Character in a StringRansom NoteConclusionLeetCode 3120 is a simple but effective problem for learning:HashSet operationsString traversalCase conversionEfficient lookup techniquesThe key idea is:Store lowercase and uppercase letters separately, then check matching pairs efficiently.Once this pattern becomes clear, many string hashing problems become much easier.

LeetCodeJavaHashSetStringEasy

Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)

🔗 Problem LinkLeetCode 345 – Reverse Vowels of a String 👉 https://leetcode.com/problems/reverse-vowels-of-a-string/IntroductionThis problem is very similar to Reverse Only Letters, but with a small twist:Instead of reversing all letters, we only reverse the vowels.At first, we might think of extracting vowels, reversing them, and putting them back. That works — but it is not the most optimal approach.In this article, we’ll:Understand the brute-force style approach (your solution)Analyze its time complexityOptimize it using the Two Pointer patternCompare both approaches📌 Problem UnderstandingYou are given a string s.You must:Reverse only the vowelsKeep all other characters in the same positionVowels include:a, e, i, o, uA, E, I, O, UExample 1Input: "IceCreAm"Output: "AceCreIm"Vowels: ['I','e','e','A'] Reversed: ['A','e','e','I']Example 2Input: "leetcode"Output: "leotcede"🧠 Your First Approach – Extract, Reverse, ReplaceYour idea:Extract all vowels into a string.Store their indices.Reverse the vowel string.Replace vowels at stored indices.Let’s look at your code.💻 Your Code (Extract & Replace Method)class Solution { public String reverseVowels(String s) { String vow = ""; List<Integer> lis = new ArrayList<>(); HashMap<Integer,Character> mp = new HashMap<>(); for(int i =0;i<s.length();i++){ if(((s.charAt(i) == 'a') || (s.charAt(i) == 'e') || (s.charAt(i) == 'i') || (s.charAt(i) == 'o') || (s.charAt(i) == 'u') || (s.charAt(i) == 'A') || (s.charAt(i) == 'E') || (s.charAt(i) == 'I') || (s.charAt(i) == 'O') || (s.charAt(i) == 'U')) ){ vow += s.charAt(i); lis.add(i); } } String so = ""; for(int i = vow.length()-1; i >= 0; i--){ so += vow.charAt(i); } for(int i =0; i< lis.size();i++){ mp.put(lis.get(i), so.charAt(i)); } String ans = ""; for(int i =0 ; i< s.length();i++){ if(mp.containsKey(i)){ ans += mp.get(i); }else{ ans += s.charAt(i); } } return ans; }}🔍 How This WorksStep 1 – Extract VowelsStore:Vowel characters in vowTheir indices in lisStep 2 – Reverse the Vowel StringCreate new reversed string so.Step 3 – Map Indices to Reversed VowelsUse a HashMap to store:index → reversed vowelStep 4 – Build Final StringTraverse original string:If index in map → use reversed vowelElse → use original character⚠️ Problem with This ApproachAlthough correct, it has inefficiencies:String concatenation (+=) → O(n²) in worst caseExtra space used:Vowel stringList of indicesHashMapFinal answer stringTime Complexity: O(n²) (due to string concatenation) Space Complexity: O(n)We can do better.🚀 Optimized Approach – Two Pointers (Best Solution)Instead of extracting vowels separately, we can:Convert string into char arrayUse two pointersSwap vowels directlyThis avoids extra structures.💻 Optimized Two Pointer Solutionclass Solution { public String reverseVowels(String s) { int i = 0, j = s.length() - 1; char[] arr = s.toCharArray(); while(i < j){ if(!isVowel(arr[i])){ i++; } else if(!isVowel(arr[j])){ j--; } else{ char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } return new String(arr); } private boolean isVowel(char c){ return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'|| c=='A'||c=='E'||c=='I'||c=='O'||c=='U'; }}🎯 Why This WorksWe:Move left pointer until vowel foundMove right pointer until vowel foundSwapContinueNo extra storage needed.⏱ Complexity ComparisonYour ApproachTime: O(n²) (string concatenation)Space: O(n)Two Pointer ApproachTime: O(n)Space: O(n) (char array)Much cleaner and faster.🔥 Key LearningThis problem reinforces:Two pointer patternIn-place modificationAvoiding unnecessary extra spaceRecognizing optimization opportunitiesWhenever you see:"Reverse something but keep other elements fixed"Think:👉 Two Pointers🏁 Final ThoughtsYour approach shows strong logical thinking:Extract → Reverse → ReplaceThat’s a valid way to solve it.But the optimized two-pointer approach is more interview-friendly.If you master this pattern, you can easily solve:Reverse Only LettersReverse StringValid PalindromeRemove Duplicates from Sorted Array

Two PointersString ManipulationHashMapLeetCodeEasy

LeetCode 3612: Process String with Special Operations I – Java StringBuilder Solution Explained

IntroductionLeetCode 3612, Process String with Special Operations I, is an excellent string simulation problem that tests your ability to process characters sequentially while maintaining a dynamic result string.The challenge introduces three special operations:* → Delete the last character# → Duplicate the current string% → Reverse the current stringAlthough the problem appears simple, it teaches an important interview concept:Simulate operations exactly as described while efficiently modifying a string.In this article, we'll break down the intuition, explore the optimal approach, perform a dry run, and analyze the time and space complexity.Problem link :- Process String with Special Operations IProblem StatementYou are given a string s containing:Lowercase English letters*#%Process the string from left to right according to the following rules:Lowercase LetterAppend it to the result.a → result += 'a'Asterisk (*)Remove the last character if one exists.abc*becomesabHash (#)Duplicate the current string.abc#becomesabcabcPercent (%)Reverse the current string.abc%becomescbaReturn the final string after processing all characters.Example 1Inputs = "a#b%*"Step-by-Step ExecutionCharacterOperationResultaAppenda#DuplicateaabAppendaab%Reversebaa*Remove lastbaOutput"ba"Key ObservationThe operations always modify the current result.We need a data structure that supports:Appendappend()Delete Last CharacterdeleteCharAt()Reversereverse()Duplicateappend(currentString)A StringBuilder supports all of these efficiently.This makes it the perfect choice for the problem.Approach 1: StringBuilder SimulationIntuitionProcess each character one by one.If it is a letterAppend it.If it is *Delete the last character.If it isDuplicate the entire current string.If it is %Reverse the current string.Continue until all characters are processed.Java Solutionclass Solution { public String processStr(String q) { StringBuilder s = new StringBuilder(); for(int i =0;i < q.length();i++){ if(q.charAt(i) != '#'&&q.charAt(i) != '*'&& q.charAt(i) != '%'){ s.append(q.charAt(i)); }else if(q.charAt(i) == '#'&& s.length()>=1){ s.append(s); }else if(q.charAt(i) == '*' && s.length()>=1){ s.deleteCharAt(s.length()-1); }else{ s.reverse(); } } return s.toString(); }}Dry RunInputs = "abc#%"Step 1aResult:aStep 2bResult:abStep 3cResult:abcStep 4#Duplicate:abcabcStep 5%Reverse:cbacbaFinal Answer:cbacbaWhy StringBuilder Is Better Than StringSuppose we use:result += ch;Every append creates a brand-new string.For large inputs this becomes inefficient.StringBuilder modifies the same object in memory.Benefits:Faster appendFaster deletionBuilt-in reverse operationLower memory overheadThis is why StringBuilder is the preferred interview solution.Complexity AnalysisLet:n = length of input stringTime ComplexityAppendO(1)Delete LastO(1)ReverseO(m)where m is current result length.DuplicateO(m)because the entire string is copied.Overall:O(n × m)In this problem:n ≤ 20so this is perfectly acceptable.Alternative Approach: Using a StackAnother way is storing characters inside a stack.Advantages:Easy handling of *Natural last-in-first-out behaviorDisadvantages:Reversing becomes expensiveDuplicating requires rebuilding dataTherefore, StringBuilder remains the cleaner solution.Interview DiscussionA common interview follow-up is:Why not use String?Because Strings are immutable.Every operation like:result += ch;creates a new object.StringBuilder avoids repeated object creation and is significantly more efficient.Edge CasesCase 1s = "z*#"Process:z → "z"* → ""# → ""Output:""Case 2s = "%"Output:""Reversing an empty string changes nothing.Case 3s = "*"Output:""Nothing exists to delete.Key TakeawaysStringBuilder is ideal for string simulation problems.Process operations strictly from left to right.append(), deleteCharAt(), and reverse() make implementation simple.Always look for mutable string structures when frequent modifications are required.Simulation problems often test implementation accuracy more than algorithmic complexity.ConclusionLeetCode 3612: Process String with Special Operations I is a clean simulation problem that demonstrates how powerful StringBuilder can be for handling dynamic string transformations.By processing each character sequentially and applying the required operation immediately, we can solve the problem efficiently with a straightforward and readable solution.This problem is an excellent exercise for improving string manipulation skills and understanding when to choose mutable data structures over immutable strings.

LeetcodeJavaStringString BuilderMedium

LeetCode 3121: Count the Number of Special Characters II – Java HashMap Solution Explained

IntroductionLeetCode 3121 – Count the Number of Special Characters II is an interesting string and hashing problem that extends the logic of the previous Special Characters problem.This problem tests:Character indexingString traversalHashMap usageUppercase and lowercase handlingOrder-based conditionsUnlike Part I, this version adds an important restriction:Every lowercase occurrence must appear before the first uppercase occurrence.This additional condition makes the problem more challenging and interview-relevant.Problem Link🔗 https://leetcode.com/problems/count-the-number-of-special-characters-ii/Problem StatementYou are given a string:wordA character is called:specialif:It appears in both lowercase and uppercaseEvery lowercase occurrence appears before the first uppercase occurrenceReturn:Number of special charactersExample 1Inputword = "aaAbcBC"Output3ExplanationSpecial characters:'a''b''c'because:Lowercase letters appear firstUppercase letters appear laterExample 2Inputword = "abc"Output:0No uppercase letters exist.Example 3Inputword = "AbBCab"Output:0Explanation:Lowercase letters appear after uppercase letters.Condition fails.Key ObservationFor a character to be special:Last lowercase index < First uppercase indexThis is the entire logic of the problem.IntuitionWe need two pieces of information.For every character:Last occurrence of lowercase letterFirst occurrence of uppercase letterIf:lastLowercase < firstUppercasethen character is special.Brute Force ApproachIdeaFor every character:Traverse entire stringFind lowercase occurrencesFind uppercase occurrencesVerify ordering conditionBrute Force ComplexityTime ComplexityO(N²)because repeated traversal is required.Space ComplexityO(1)Optimized HashMap ApproachIdeaUse two HashMaps:Lowercase map stores last indexUppercase map stores first indexThen compare indices.Java Solutionclass Solution { public int numberOfSpecialChars(String word) { HashMap<Character, Integer> lower = new HashMap<>(); HashMap<Character, Integer> upper = new HashMap<>(); for(int i = 0; i < word.length(); i++) { if(word.charAt(i) >= 'a' && word.charAt(i) <= 'z') { lower.put(word.charAt(i), i); } else { if(!upper.containsKey(word.charAt(i))) { upper.put(word.charAt(i), i); } } } int ans = 0; for(int i = 0; i < word.length(); i++) { char up = Character.toUpperCase(word.charAt(i)); if(lower.containsKey(word.charAt(i)) && upper.containsKey(up)) { if(lower.get(word.charAt(i)) < upper.get(up)) { ans++; lower.remove(word.charAt(i)); upper.remove(up); } } } return ans; }}Cleaner Optimized Versionclass Solution { public int numberOfSpecialChars(String word) { int[] lastLower = new int[26]; int[] firstUpper = new int[26]; Arrays.fill(lastLower, -1); Arrays.fill(firstUpper, Integer.MAX_VALUE); for(int i = 0; i < word.length(); i++) { char ch = word.charAt(i); if(Character.isLowerCase(ch)) { lastLower[ch - 'a'] = i; } else { firstUpper[ch - 'A'] = Math.min(firstUpper[ch - 'A'], i); } } int count = 0; for(int i = 0; i < 26; i++) { if(lastLower[i] != -1 && firstUpper[i] != Integer.MAX_VALUE && lastLower[i] < firstUpper[i]) { count++; } } return count; }}Why This WorksFor every character:We store:last lowercase positionand:first uppercase positionThen simply check:lastLowercase < firstUppercaseIf true:Character satisfies problem condition.Dry RunInputword = "aaAbcBC"Step 1: Store IndicesLowercase positions:'a' → 1'b' → 3'c' → 4Uppercase positions:'A' → 2'B' → 5'C' → 6Step 2: Compare1 < 2 → valid3 < 5 → valid4 < 6 → validCount becomes:3Final Answer3Time Complexity AnalysisOptimized HashMap SolutionTime ComplexityO(N)because string traversal happens once.Space ComplexityO(1)Maximum alphabet size remains fixed.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(1)HashMap / Array ApproachO(N)O(1)Interview ExplanationIn interviews, explain:A character is special only if its last lowercase occurrence appears before its first uppercase occurrence. We track indices efficiently using HashMaps or arrays.This demonstrates:String manipulation skillsIndex trackingHashing knowledgeOptimization thinkingCommon Mistakes1. Checking Only PresenceMany solutions only verify:lowercase exists && uppercase existsBut ordering condition is also required.2. Storing Wrong IndicesWe need:Last lowercase indexFirst uppercase indexnot the opposite.3. Double Counting CharactersAlways remove counted characters or use controlled traversal.4. Ignoring Case ConversionAlways convert correctly using:Character.toUpperCase(ch)FAQsQ1. Why store last lowercase occurrence?Because all lowercase letters must appear before uppercase.Q2. Why store first uppercase occurrence?Because it defines the earliest uppercase appearance.Q3. Can arrays replace HashMaps?Yes.Arrays are even more optimized because alphabet size is fixed.Q4. Is this problem interview important?Yes.It tests:String traversalIndex trackingCharacter handlingOptimization techniquesRelated ProblemsPractice these next:Count the Number of Special Characters IFirst Unique Character in a StringValid AnagramConclusionLeetCode 3121 is an excellent medium-level hashing and string problem.It teaches:Efficient index trackingHashMap usageOrder-based validationCharacter manipulationThe key insight is:A character is special only if its last lowercase occurrence appears before its first uppercase occurrence.Once this pattern becomes clear, many advanced string indexing problems become much easier.

LeetCodeJavaHashMapStringMedium

Longest Substring with K Unique Characters – Efficient Sliding Window Solution

IntroductionFinding substrings with unique characters is a common problem in string manipulation and interview questions.GFG’s Longest Substring with K Unique Characters problem challenges you to find the length of the longest substring containing exactly K distinct characters.The focus is not just on brute-force solutions, but on using sliding window with a HashMap to efficiently track character frequencies and window boundaries.If you’d like to try solving the problem first, you can attempt it here: Try the problem on GeeksforGeeks: https://leetcode.com/problems/max-consecutive-ones-iii/Problem UnderstandingYou are given:A string s of lowercase lettersAn integer kYour task: Return the length of the longest substring containing exactly k distinct characters.Examples:Input: s = "aabacbebebe", k = 3Output: 7Explanation: "cbebebe" is the longest substring with 3 distinct characters.Input: s = "aaaa", k = 2Output: -1Explanation: No substring contains exactly 2 distinct characters.Input: s = "aabaaab", k = 2Output: 7Explanation: "aabaaab" has exactly 2 unique characters.A naive approach would try all possible substrings, count unique characters, and track the max length.Time Complexity: O(n²)Inefficient for large stringsKey Idea: Sliding Window + HashMapInstead of recomputing the unique characters for every substring:Use a HashMap to store character frequencies in the current windowUse two pointers (i and j) to maintain the windowExpand the window by moving j and add characters to the mapShrink the window from the left when the number of unique characters exceeds kUpdate the max length whenever the window has exactly k unique charactersThis ensures each character is processed only once, giving a linear solution.Approach (Step-by-Step)Initialize a HashMap mp to store character countsUse two pointers i (window start) and j (window end)Iterate over the string with jAdd s[j] to the map and update its countCheck the map size:If size < k → move j forwardIf size == k → update max length, move j forwardIf size > k → shrink window from i until map size <= kAfter iterating, return max (or -1 if no valid substring exists)Optimization:Using a HashMap avoids recalculating the number of unique characters for every substringSliding window ensures O(n) complexityImplementation (Java)class Solution {public int longestKSubstr(String s, int k) {HashMap<Character,Integer> mp = new HashMap<>();int i = 0, j = 0;int max = -1;while (j < s.length()) {// Add current character to mapmp.put(s.charAt(j), mp.getOrDefault(s.charAt(j), 0) + 1);if (mp.size() < k) {j++;}else if (mp.size() == k) {// Update max length when exactly k unique charactersmax = Math.max(max, j - i + 1);j++;}else {// Shrink window until map size <= kwhile (mp.size() > k) {mp.put(s.charAt(i), mp.get(s.charAt(i)) - 1);if (mp.get(s.charAt(i)) == 0) {mp.remove(s.charAt(i));}i++;}max = Math.max(max, j - i + 1);j++;}}return max;}}Dry Run ExampleInput:s = "aabacbebebe", k = 3Execution:Window [0-4] = "aaba" → unique = 2 → continueWindow [1-6] = "abacb" → unique = 3 → max = 5Window [4-10] = "cbebebe" → unique = 3 → max = 7Output:7Complexity AnalysisTime Complexity: O(n) → Each character enters and leaves the window onceSpace Complexity: O(k) → HashMap stores at most k unique charactersEdge Cases Consideredk greater than number of unique characters → return -1Entire string has exactly k unique charactersString with repeated characters onlyMinimum string length (1)Sliding Window Pattern ImportanceThis problem reinforces a common sliding window + hashmap pattern used in:Longest substring problems with constraintsCounting substrings with exactly K conditionsOptimizing brute-force approaches to linear solutionsConclusionBy combining sliding window with HashMap frequency tracking, we reduce an O(n²) problem to O(n).Once you master this approach, many string and substring problems with constraints on unique characters become much easier to solve efficiently.

SlidingWindowHashMapStringsGFG

LeetCode 1190 Reverse Substrings Between Each Pair of Parentheses – Java Solution & Explanation

IntroductionLeetCode 1190 – Reverse Substrings Between Each Pair of Parentheses is a string manipulation problem that requires reversing the substring inside every matching pair of parentheses.The important part is that reversals must happen from the innermost parentheses outward.For example:(u(love)i)The substring love is reversed first:(u(evol)i)Then the complete content inside the outer parentheses is reversed, producing:iloveuThe final answer should contain only the letters. All parentheses must be removed.A stack is useful here because it allows the opening parenthesis of the current substring to be tracked until its matching closing parenthesis is encountered.ProblemQuestion Link-: Reverse Substrings Between Each Pair of ParenthesesGiven a string s containing lowercase English letters and parentheses, reverse the strings inside each pair of matching parentheses, starting from the innermost pair.Return the resulting string without any parentheses.ExampleInput:s = "(u(love)i)"Output:"iloveu"Another example:Input:s = "(ed(et(oc))el)"Output:"leetcode"ApproachThe key observation is that when a closing parenthesis ) is encountered, the substring belonging to the most recently opened parenthesis needs to be reversed first.This naturally matches the behavior of a stack.Step 1: Store opening parenthesesWhenever ( is encountered, its index is pushed onto the stack.For example:(ed(et(oc))el)When reaching nested opening parentheses, the stack stores their positions.The most recently added opening parenthesis belongs to the innermost substring.Step 2: Process a closing parenthesisWhen ) is encountered:Get the index of the matching ( from the top of the stack.Reverse the characters between those two parentheses.Remove the opening parenthesis index from the stack.For example:(oc)When ) is reached, oc is reversed:coThe same process then happens for the next outer pair.Step 3: Remove the parenthesesAfter all reversals are complete, the character array still contains ( and ).The final traversal simply collects all characters except the parentheses.Java SolutionThe following solution uses a Stack<Integer> to keep track of opening-parenthesis positions and a character array so that the reversals can be performed directly on the string representation.class Solution { public void rev(char[] s, int en, int st) { String rev = ""; for (int i = en; i >= st; i--) { rev += s[i]; } int co = 0; for (int i = st; i <= en; i++) { s[i] = rev.charAt(co); co++; } } public String reverseParentheses(String s) { Stack<Integer> st = new Stack<>(); char[] sa = s.toCharArray(); for (int i = 0; i < sa.length; i++) { if (sa[i] == '(') { st.push(i); } if (sa[i] == ')') { int star = st.peek(); rev(sa, i, star + 1); st.pop(); } } String an = ""; for (int i = 0; i < sa.length; i++) { if (sa[i] != ')' && sa[i] != '(') { an += sa[i]; } } return an; }}How the Code Worksrev() methodThe rev() method receives:s → character arrayen → ending indexst → starting indexIt first builds the reversed substring:for (int i = en; i >= st; i--) { rev += s[i];}Then the reversed characters are copied back into the original character array:for (int i = st; i <= en; i++) { s[i] = rev.charAt(co); co++;}This changes the substring directly inside the character array.Stack processingThe main method scans the string from left to right.When an opening parenthesis is found:if (sa[i] == '(') { st.push(i);}Its index is stored in the stack.When a closing parenthesis is found:if (sa[i] == ')') { int star = st.peek(); rev(sa, i, star + 1); st.pop();}The top of the stack gives the matching opening parenthesis.The substring between them is reversed, and then the opening parenthesis is removed from the stack.This automatically processes nested parentheses from the inside out.Dry RunConsider:s = "(u(love)i)"Initial character array:(u(love)i)1. First (Its index is pushed onto the stack.Stack:[0]2. Second (The opening parenthesis before love is pushed.Stack:[0, 2]3. First )The top of the stack is index 2.The substring between index 3 and 6 is:loveReverse it:evolNow the string is effectively:(u(evol)i)The inner opening parenthesis is removed from the stack.Stack:[0]4. Final )The remaining opening parenthesis corresponds to the outer substring.Its contents are now:uevoliReverse it:iloveuFinally, the parentheses are removed.Result:iloveuWhy a Stack WorksThe problem specifically says to process the innermost parentheses first.A stack follows Last In, First Out (LIFO).For:(ed(et(oc))el)the opening parentheses are encountered in order:(((The last opening parenthesis belongs to:(oc)Therefore, it must be processed first.The stack gives exactly this behavior:Last opened ↓ (oc) ↓ (etco) ↓(edoc...el)This is why a stack is a natural data structure for this problem.Complexity AnalysisLet n be the length of the input string.The stack operations themselves take O(n) time.However, the actual reversal is performed every time a closing parenthesis is encountered. In the provided implementation, the rev() method also builds a temporary String using repeated concatenation.Therefore, the worst-case time complexity of this implementation can reach O(n²).The final construction also uses:an += sa[i];Repeated string concatenation can additionally introduce quadratic behavior in Java.Time ComplexityO(n²) worst caseSpace ComplexityO(n)The stack and character array require linear auxiliary space.A Useful OptimizationThe overall idea is correct, but two parts of the implementation can be improved:String rev = "";andan += sa[i];Since Java String objects are immutable, repeated concatenation can create many intermediate strings.A StringBuilder is generally more appropriate for repeated character construction.The core stack-based idea, however, remains the same.Interview TipWhen a string problem involves nested structures, ask whether the processing order follows the structure of a stack.For parentheses:((()))the last opened section is the first one that must be completed.That is a strong signal for using a stack.A useful pattern to remember is:Opening bracket → push its positionClosing bracket → use the latest opening positionProcess inner section → popRecognizing this pattern can make similar nested-string and bracket problems much easier to approach.ConclusionLeetCode 1190 demonstrates how a simple stack can handle nested string operations efficiently at the algorithmic level.The main idea is to store the positions of opening parentheses and, whenever a closing parenthesis appears, reverse the substring associated with the most recently opened pair.The important pattern is:Opening parenthesis → push indexClosing parenthesis → reverse current substring → popFinal pass → remove parenthesesThis approach provides a straightforward way to process nested parentheses from the inside out while keeping the implementation relatively simple in Java.

LeetCodeJavaStackStringsParenthesesMedium

LeetCode 387: First Unique Character in a String – Java HashMap Solution Explained

IntroductionLeetCode 387 – First Unique Character in a String is one of the most common beginner-friendly string and hashing interview problems.This problem helps developers understand:Frequency countingHashMap usageString traversalCharacter manipulationEfficient lookup techniquesIt is frequently asked in coding interviews because it tests both:Logical thinkingTime complexity optimizationProblem Link🔗 https://leetcode.com/problems/first-unique-character-in-a-string/Problem StatementGiven a string:sReturn:Index of the first non-repeating characterIf no unique character exists:Return -1Example 1Inputs = "leetcode"Output0Explanation:'l'appears only once and is the first unique character.Example 2Inputs = "loveleetcode"Output2Explanation:'v'is the first character that appears only once.Example 3Inputs = "aabb"Output-1All characters repeat.IntuitionTo identify the first unique character:We first need to know:How many times every character appearsA HashMap is perfect for frequency counting.After counting:We traverse the string again and return the first character whose frequency is:1Brute Force ApproachIdeaFor every character:Traverse the entire stringCount occurrencesReturn the first character with count = 1Brute Force ComplexityTime ComplexityO(N²)because nested traversal is required.Space ComplexityO(1)Optimized HashMap ApproachIdeaUse a HashMap to store:character → frequencyThen scan the string again.The first character with frequency:1is the answer.Java Solutionclass Solution {public int firstUniqChar(String s) {HashMap<Character, Integer> mp = new HashMap<>();for(int i = 0; i < s.length(); i++) {mp.put(s.charAt(i), mp.getOrDefault(s.charAt(i), 0) + 1);}for(int i = 0; i < s.length(); i++) {if(mp.get(s.charAt(i)) == 1) {return i;}}return -1;}}Cleaner Optimized Versionclass Solution {public int firstUniqChar(String s) {int[] freq = new int[26];for(char ch : s.toCharArray()) {freq[ch - 'a']++;}for(int i = 0; i < s.length(); i++) {if(freq[s.charAt(i) - 'a'] == 1) {return i;}}return -1;}}Why This WorksThe algorithm works in two passes.First PassStore frequency of every character.Example:"leetcode"Frequency map:l → 1e → 3t → 1c → 1o → 1d → 1Second PassTraverse string from left to right.The first character whose frequency equals:1is returned.Dry RunInputs = "loveleetcode"Step 1: Frequency Countingl → 2o → 2v → 1e → 4t → 1c → 1d → 1Step 2: Traverse AgainIndex 0:'l' → frequency 2Index 1:'o' → frequency 2Index 2:'v' → frequency 1Return:2Time Complexity AnalysisOptimized HashMap SolutionTime ComplexityO(N)because string traversal happens twice.Space ComplexityO(1)Only lowercase English letters exist.Maximum storage remains fixed.Brute Force vs OptimizedApproachTime ComplexitySpace ComplexityBrute ForceO(N²)O(1)HashMap / Frequency ArrayO(N)O(1)Interview ExplanationIn interviews, explain:We use a frequency map to count occurrences of every character. Then we scan the string again to locate the first character whose frequency is exactly one.This demonstrates:Hashing knowledgeFrequency countingEfficient lookup usageOptimization skillsCommon Mistakes1. Returning Character Instead of IndexThe problem asks for:indexnot the character itself.2. Using Nested LoopsNested traversal increases complexity unnecessarily.3. Forgetting Second TraversalHashMap only stores frequencies.You still need:left-to-right traversalto find the first unique character.FAQsQ1. Why use HashMap?Because frequency lookup becomes very efficient.Q2. Can we use arrays instead?Yes.Since only lowercase letters exist:int[26]works perfectly.Q3. Why traverse the string twice?First pass counts frequency.Second pass preserves original order.Q4. Is this problem important for interviews?Yes.It is one of the most common hashing interview questions.Related ProblemsPractice these next:Valid AnagramRansom NoteCount the Number of Special CharactersConclusionLeetCode 387 is an excellent beginner-level problem for learning:Frequency countingHashMap usageString traversalEfficient lookup techniquesThe key insight is:Count character frequencies first, then find the first character with frequency equal to one.This pattern is widely used in many real interview problems involving strings and hashing.

LeetCodeJavaHashMapStringEasy

LeetCode 290: Word Pattern – Multiple Ways to Verify Bijection Between Pattern Characters and Words

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/word-pattern/Problem DescriptionYou are given:A string patternA string sThe string s consists of words separated by spaces.Your task is to determine whether s follows the same pattern defined by the string pattern.To follow the pattern, there must be a bijection between pattern characters and words.Understanding the Meaning of BijectionA bijection means a one-to-one relationship between two sets.For this problem it means:Every character in the pattern maps to exactly one word.Every word maps to exactly one pattern character.Two characters cannot map to the same word.Two words cannot map to the same character.This ensures the mapping is unique in both directions.Example WalkthroughExample 1Inputpattern = "abba"s = "dog cat cat dog"OutputtrueExplanationMapping:a → dogb → catPattern:a b b aWords:dog cat cat dogThe mapping is perfectly consistent.Example 2Inputpattern = "abba"s = "dog cat cat fish"OutputfalseExplanationThe last word "fish" breaks the pattern because "a" was already mapped to "dog".Example 3Inputpattern = "aaaa"s = "dog cat cat dog"OutputfalseExplanationPattern requires:a → same word every timeBut the words differ.Constraints1 <= pattern.length <= 300pattern contains lowercase English letters1 <= s.length <= 3000s contains lowercase letters and spaceswords are separated by a single spaceno leading or trailing spacesCore ObservationBefore applying any algorithm, we should verify one simple condition.If the number of pattern characters does not match the number of words, then the pattern cannot match.Example:pattern = "abba"s = "dog cat dog"Pattern length = 4Words = 3This automatically returns false.Thinking About Possible ApproachesWhile solving this problem, several strategies may come to mind:Use one HashMap to store pattern → word mapping and check duplicates manually.Use two HashMaps to enforce bijection from both directions.Track first occurrence indices of pattern characters and words.Compare mapping patterns using arrays or maps.Let’s explore these approaches one by one.Approach 1: Single HashMap (Your Solution)IdeaWe store mapping:pattern character → wordWhile iterating:If the character already exists in the map→ check if it maps to the same word.If it does not exist→ ensure that no other character already maps to that word.This ensures bijection.Java Implementationclass Solution { public boolean wordPattern(String pattern, String s) { String words[] = s.split(" "); // Length mismatch means impossible mapping if(pattern.length() != words.length) return false; HashMap<Character,String> mp = new HashMap<>(); for(int i = 0; i < words.length; i++){ char ch = pattern.charAt(i); if(mp.containsKey(ch)){ if(!mp.get(ch).equals(words[i])){ return false; } }else{ // Prevent two characters mapping to same word if(mp.containsValue(words[i])){ return false; } } mp.put(ch, words[i]); } return true; }}Time ComplexityO(n²)Because containsValue() can take O(n) time in worst case.Space ComplexityO(n)Approach 2: Two HashMaps (Cleaner Bijection Enforcement)IdeaInstead of checking containsValue, we maintain two maps.pattern → wordword → patternThis ensures bijection naturally.Java Implementationclass Solution { public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if(pattern.length() != words.length) return false; HashMap<Character, String> map1 = new HashMap<>(); HashMap<String, Character> map2 = new HashMap<>(); for(int i = 0; i < pattern.length(); i++){ char ch = pattern.charAt(i); String word = words[i]; if(map1.containsKey(ch) && !map1.get(ch).equals(word)) return false; if(map2.containsKey(word) && map2.get(word) != ch) return false; map1.put(ch, word); map2.put(word, ch); } return true; }}Time ComplexityO(n)Because both maps allow constant-time lookups.Space ComplexityO(n)Approach 3: Index Mapping Technique (Elegant Trick)IdeaAnother clever technique is to compare first occurrence indices.Example:pattern = abbawords = dog cat cat dogPattern index sequence:a → 0b → 1b → 1a → 0Words index sequence:dog → 0cat → 1cat → 1dog → 0If the index sequences match, then the pattern holds.Java Implementationclass Solution { public boolean wordPattern(String pattern, String s) { String[] words = s.split(" "); if(pattern.length() != words.length) return false; HashMap<Character,Integer> map1 = new HashMap<>(); HashMap<String,Integer> map2 = new HashMap<>(); for(int i = 0; i < pattern.length(); i++){ char ch = pattern.charAt(i); String word = words[i]; if(!map1.getOrDefault(ch, -1) .equals(map2.getOrDefault(word, -1))){ return false; } map1.put(ch, i); map2.put(word, i); } return true; }}Time ComplexityO(n)Space ComplexityO(n)Comparison of ApproachesApproachTime ComplexitySpace ComplexityNotesSingle HashMapO(n²)O(n)Simple but slowerTwo HashMapsO(n)O(n)Cleaner bijection enforcementIndex MappingO(n)O(n)Elegant and interview-friendlyKey Interview InsightProblems like this test your understanding of:Bijection MappingSimilar problems include:Isomorphic StringsWord Pattern IISubstitution Cipher ProblemsUnderstanding how to enforce one-to-one mappings is a powerful technique.ConclusionThe Word Pattern problem is an excellent example of how HashMaps can enforce relationships between two datasets.While a simple HashMap solution works, more optimized methods like two-way mapping or index comparison provide cleaner and more efficient implementations.Mastering these techniques will help you solve many pattern-matching and mapping problems commonly asked in coding interviews.

HashMapString ManipulationBijection MappingTwo HashMapsIndex MappingLeetCode Easy

LeetCode 1047: Remove All Adjacent Duplicates In String — Java Solution With All Approaches Explained

Introduction: What Is LeetCode 1047 Remove All Adjacent Duplicates In String?If you are grinding LeetCode for coding interviews at companies like Google, Amazon, or Microsoft, LeetCode 1047 Remove All Adjacent Duplicates In String is a problem you cannot skip. It is one of the most elegant examples of the stack simulation pattern and appears frequently as a warmup or follow-up question in technical rounds.In this article we will cover everything you need — plain English explanation, real life analogy, 3 Java approaches with dry runs, complexity analysis, common mistakes, FAQs, and similar problems to practice next.Here is the problem link-: Leetcode 1047 What Is the Problem Really Asking?You are given a string. Keep scanning it and whenever you find two same letters sitting next to each other, remove both of them. After removing, the letters around them might now become adjacent and form a new pair — so you keep doing this until no more adjacent duplicates exist.Example walkthrough for "abbaca":"abbaca" → bb are adjacent duplicates → remove → "aaca""aaca" → aa are adjacent duplicates → remove → "ca""ca" → no adjacent duplicates → done!✅ Output: "ca"Real Life Analogy — Think of Popping BubblesImagine a row of colored bubbles. Whenever two bubbles of the same color are next to each other, they pop and disappear. After they pop, the bubbles on either side might now touch each other — and if they are the same color, they pop too! You keep going until no two same-colored bubbles are touching.That chain reaction is exactly what this problem simulates. And the best tool to handle that chain reaction? A stack.Approach 1: Brute Force (Beginner Friendly)The IdeaScan the string repeatedly. Every time you find two adjacent equal characters, remove them. Keep doing this until a full pass finds nothing to remove.public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(s); boolean found = true; while (found) { found = false; for (int i = 0; i < sb.length() - 1; i++) { if (sb.charAt(i) == sb.charAt(i + 1)) { sb.deleteCharAt(i); sb.deleteCharAt(i); found = true; break; } } } return sb.toString();}This is easy to understand but very slow. For each pair found, you restart the entire scan. With n up to 100,000, this will get Time Limit Exceeded on LeetCode. Use it only to build intuition.Time Complexity: O(n²) — repeated passes over the string Space Complexity: O(n) — StringBuilder storageApproach 2: Stack Based Solution (Classic Interview Approach)The IdeaA stack is perfect here because of one key observation — when you remove a pair, the character that was before the pair is now adjacent to the character after the pair. That is a Last In First Out situation, which is exactly what a stack handles naturally.Algorithm:If the current character matches the top of the stack → pop (they cancel each other)Otherwise → push the current character onto the stackAt the end, the stack contains your final answerpublic String removeDuplicates(String s) { Stack<Character> st = new Stack<>(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (!st.empty() && c == st.peek()) { st.pop(); // adjacent duplicate found, cancel both } else { st.push(c); } } while (!st.empty()) { sb.append(st.pop()); } return sb.reverse().toString();}Dry Run — "abbaca"We go character by character and check against the top of the stack:a → stack empty, push → stack: [a]b → top is a, not equal, push → stack: [a, b]b → top is b, equal! pop → stack: [a]a → top is a, equal! pop → stack: []c → stack empty, push → stack: [c]a → top is c, not equal, push → stack: [c, a]Stack remaining: [c, a] → reverse → ✅ "ca"Notice how after removing bb, the two as automatically become adjacent and get caught — the stack handles this chain reaction naturally without any extra logic!Time Complexity: O(n) — single pass through the string Space Complexity: O(n) — stack holds up to n charactersApproach 3: StringBuilder as Stack (Optimal Solution) ✅The IdeaThis is your own solution and the best one! Instead of using a separate Stack<Character>, we use StringBuilder itself as a stack:sb.append(c) acts as pushsb.deleteCharAt(sb.length() - 1) acts as popsb.charAt(sb.length() - 1) acts as peekNo extra data structure, no boxing of char into Character objects, and no reversal needed at the end. Clean, fast, and minimal.public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (sb.length() != 0 && c == sb.charAt(sb.length() - 1)) { sb.deleteCharAt(sb.length() - 1); // adjacent duplicate, remove both } else { sb.append(c); } } return sb.toString();}Dry Run — "azxxzy"a → sb empty, append → "a"z → last char is a, not equal, append → "az"x → last char is z, not equal, append → "azx"x → last char is x, equal! delete → "az"z → last char is z, equal! delete → "a"y → last char is a, not equal, append → "ay"✅ Final Answer: "ay"Again, notice the chain reaction — after xx was removed, z and z became adjacent and got removed too. The StringBuilder handles this perfectly in a single pass!Time Complexity: O(n) — one pass, every character processed exactly once Space Complexity: O(n) — StringBuilder storageWhy StringBuilder Beats Stack in JavaWhen you use Stack<Character> in Java, every char primitive gets auto-boxed into a Character object. That means extra memory allocation for every single character. With StringBuilder, you work directly on the underlying char array — faster and leaner. Plus you skip the reversal step entirely.For an interview, the Stack approach is great for explaining your thought process clearly. But for the final submitted solution, StringBuilder is the way to go.Common Mistakes to AvoidNot checking sb.length() != 0 before peeking If the StringBuilder is empty and you call sb.charAt(sb.length() - 1), you will get a StringIndexOutOfBoundsException. Always guard this check — even if the problem guarantees valid input, it shows clean coding habits.Thinking you need multiple passes Many beginners think you need to scan the string multiple times because of chain reactions. The stack handles chain reactions automatically in a single pass. Trust the process!Forgetting to reverse when using Stack Since a stack gives you characters in reverse order when you pop them, you must call .reverse() at the end. With StringBuilder you do not need this.How This Fits Into the Stack Simulation PatternBy now you might be noticing a theme across multiple problems:LeetCode 3174 Clear Digits — digit acts as backspace, deletes closest left non-digit LeetCode 2390 Removing Stars — star acts as backspace, deletes closest left non-star LeetCode 1047 Remove Adjacent Duplicates — character cancels itself if it matches the top of stackAll three use the exact same StringBuilder-as-stack pattern. The only difference is the condition that triggers a deletion. This is why pattern recognition is the real skill — once you internalize this pattern, you can solve a whole family of problems in minutes.FAQs — People Also AskQ1. What is the best approach for LeetCode 1047 in Java? The StringBuilder approach is the best. It runs in O(n) time, uses O(n) space, requires no extra data structure, and avoids the reversal step needed with a Stack.Q2. Why does a stack work for removing adjacent duplicates? Because whenever you remove a pair, the characters around them become the new neighbors. A stack naturally keeps track of the most recently seen character, so it catches these chain reactions without any extra logic.Q3. What is the time complexity of LeetCode 1047? The optimal solution runs in O(n) time and O(n) space, where n is the length of the input string.Q4. Is LeetCode 1047 asked in coding interviews? Yes, it is commonly asked as a warmup problem or follow-up at companies like Google, Amazon, and Adobe. It tests your understanding of stack-based string manipulation.Q5. What is the difference between LeetCode 1047 and LeetCode 1209? LeetCode 1047 removes pairs of adjacent duplicates. LeetCode 1209 is the harder version — it removes groups of k adjacent duplicates, requiring you to store counts alongside characters in the stack.Similar LeetCode Problems to Practice Next2390. Removing Stars From a String — Medium — star as backspace3174. Clear Digits — Easy — digit as backspace844. Backspace String Compare — Easy — compare two strings after backspaces1209. Remove All Adjacent Duplicates in String II — Medium — harder version with k duplicates735. Asteroid Collision — Medium — stack simulation with collision logicConclusionLeetCode 1047 Remove All Adjacent Duplicates In String is a beautiful problem that teaches you one of the most powerful and reusable patterns in DSA — stack simulation. The moment you spot that a removal can cause a chain reaction of more removals, you know a stack is your best friend.The StringBuilder solution is clean, optimal, and interview-ready. Master it, understand why it works, and you will be able to tackle the entire family of stack simulation problems with confidence.Found this helpful? Share it with friends preparing for coding interviews

LeetCodeJavaStackStringEasy

LeetCode 3751: Total Waviness of Numbers in Range I – Java Solution with Dry Run and Explanation

IntroductionLeetCode 3751 introduces an interesting digit-based pattern problem where we calculate the total waviness of numbers inside a given range.This problem combines:Digit traversalPattern recognitionPeaks and valleys logicString manipulationBrute force iterationThe problem is straightforward once we clearly understand how peaks and valleys work.Problem StatementYou are given two integers:num1 and num2representing the inclusive range:[num1, num2]For every number:A digit is called a peak if it is strictly greater than both neighbors.A digit is called a valley if it is strictly smaller than both neighbors.The first and last digits can never be peaks or valleys.Return the total waviness across all numbers in the range.ExampleInputnum1 = 120num2 = 130Output3ExplanationNumbers contributing to waviness:120 → 2 is a peak → waviness = 1121 → 2 is a peak → waviness = 1130 → 3 is a peak → waviness = 1Total:1 + 1 + 1 = 3Understanding Peaks and ValleysPeak ConditionA digit is a peak if:digit > left neighborANDdigit > right neighborExample:484Here:8 > 48 > 4So 8 is a peak.Valley ConditionA digit is a valley if:digit < left neighborANDdigit < right neighborExample:202Here:0 < 20 < 2So 0 is a valley.Key ObservationWe only need to check:index 1 to length-2because:First digit has no left neighborLast digit has no right neighborIntuitionThe simplest way:Iterate through every number in the rangeConvert number into charactersCheck each middle digitCount peaks and valleysAdd to final answerSince constraints are small:num2 <= 10^5a brute force approach works efficiently.Java Solutionclass Solution { public int totalWaviness(int num1, int num2) { int ans = 0; if(num1 == num2) { int temp = num1; String c = Integer.toString(temp); char[] arr = c.toCharArray(); for(int i = 1; i < arr.length - 1; i++) { if((arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) || (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])) { ans++; } } return ans; } for(int i = num1; i <= num2; i++) { String c = Integer.toString(i); char[] carr = c.toCharArray(); for(int j = 1; j < carr.length - 1; j++) { if((carr[j] < carr[j - 1] && carr[j] < carr[j + 1]) || (carr[j] > carr[j - 1] && carr[j] > carr[j + 1])) { ans++; } } } return ans; }}Step-by-Step ExplanationStep 1: Iterate Through Rangefor(int i = num1; i <= num2; i++)Process every number.Step 2: Convert Number to Character ArrayString c = Integer.toString(i);char[] carr = c.toCharArray();This makes digit comparison easier.Step 3: Check Middle Digitsfor(int j = 1; j < carr.length - 1; j++)Skip first and last digits.Step 4: Check Peak or Valley(carr[j] < carr[j-1] && carr[j] < carr[j+1])OR(carr[j] > carr[j-1] && carr[j] > carr[j+1])If true:ans++;Dry RunInputnum1 = 198num2 = 202Number 198Digits:1 9 8Check 9:9 > 19 > 8Peak found.Waviness:1Number 1991 9 99 is not strictly greater than right neighbor.No waviness.Number 2012 0 10 is smaller than both neighbors.Valley found.Number 2022 0 2Again:0 < 20 < 2Valley found.Final Answer198 → 1201 → 1202 → 1Total = 3Time Complexity AnalysisLet:N = num2 - num1 + 1D = number of digitsTime ComplexityO(N × D)At most:D = 6which is very small.Efficient for constraints.Space ComplexityO(D)due to character array conversion.Why Brute Force Works HereConstraints are small:num2 <= 100000So checking every number directly is acceptable.For larger constraints:Digit DP would be needed.But here:Simplicity is better.Common Mistakes1. Including First or Last DigitThese digits cannot be peaks or valleys.2. Using Non-Strict ComparisonWrong:>=<=Correct:><because definition says:strictly greaterstrictly smaller3. Forgetting Both ConditionsNeed to check:PeakValleyEdge CasesSingle Digit NumbersWaviness:0because fewer than 3 digits.Repeated DigitsExample:111No peak or valley.Alternating DigitsExample:4848Produces multiple waviness counts.Interview ExplanationIn interviews explain:Since the constraints are small, we can directly iterate through every number, convert it into digits, and count peaks and valleys by checking neighboring digits.This demonstrates:Observation skillsConstraint analysisClean implementationConclusionLeetCode 3751 is a clean implementation problem focused on:Digit traversalPattern recognitionPeaks and valleysBrute force optimizationThe key insight is:A digit contributes to waviness only if it is strictly greater or strictly smaller than both immediate neighbors.Once this condition is understood, the implementation becomes very straightforward.

LeetCodeJavaStringPeaks and ValleysBrute Force SolutionDigit ProblemsMediumArray

Find the Difference – Smart ASCII Sum Trick (LeetCode 389)

🔗 Problem LinkLeetCode 389 – Find the Difference 👉 https://leetcode.com/problems/find-the-difference/IntroductionThis is a very clever problem.At first glance, you might think:Use a HashMapCount frequenciesCompare both stringsBut there’s a much smarter and cleaner way to solve it using character arithmetic (ASCII values).This problem teaches an important lesson:Sometimes math can replace extra space.Let’s break it down.📌 Problem UnderstandingYou are given two strings:stString t is created by:Shuffling string sAdding one extra character at a random positionYour task:Return the extra character added to t.Example 1Input: s = "abcd" t = "abcde"Output: "e"Example 2Input: s = "" t = "y"Output: "y"🧠 First Intuition (Brute Force Thinking)When solving this for the first time, a common approach would be:Count frequency of characters in sCount frequency of characters in tCompare bothThe one with extra count is the answerThat works in O(n) time and O(26) space.But we can do better.🚀 Smarter Approach – ASCII Sum Trick💡 Key InsightCharacters are stored as integer ASCII values.If:We add all ASCII values of characters in tSubtract all ASCII values of characters in sWhat remains?👉 The ASCII value of the extra character.Because:All matching characters cancel out.Only the added character remains.💻 Your Codeclass Solution { public char findTheDifference(String s, String t) { int tot = 0; for(int i = 0; i < t.length(); i++){ tot += (int)t.charAt(i); } for(int i = 0; i < s.length(); i++){ tot -= (int)s.charAt(i); } return (char)tot; }}🔍 Step-by-Step Explanation1️⃣ Initialize Totalint tot = 0;This will store the running ASCII difference.2️⃣ Add All Characters of ttot += (int)t.charAt(i);We add ASCII values of every character in t.3️⃣ Subtract All Characters of stot -= (int)s.charAt(i);We subtract ASCII values of every character in s.4️⃣ Return Remaining Characterreturn (char)tot;After subtraction, only the extra character’s ASCII value remains.We convert it back to char.🎯 Why This WorksLet’s take example:s = "abcd"t = "abcde"ASCII Sum:t = a + b + c + d + es = a + b + c + dSubtract:(t sum) - (s sum) = eEverything cancels except the extra letter.Simple and powerful.⏱ Complexity AnalysisTime Complexity: O(n)One loop over tOne loop over sSpace Complexity: O(1)No extra data structure used.🔥 Even Smarter Approach – XOR TrickAnother elegant method is using XOR:Why XOR Works?Properties:a ^ a = 0a ^ 0 = aXOR is commutativeIf we XOR all characters in both strings:Matching characters cancel out.Only the extra character remains.XOR Versionclass Solution { public char findTheDifference(String s, String t) { char result = 0; for(char c : s.toCharArray()){ result ^= c; } for(char c : t.toCharArray()){ result ^= c; } return result; }}This is considered the most elegant solution.🏁 Final ThoughtsThis problem teaches:Thinking beyond brute forceUsing mathematical propertiesUnderstanding ASCII representationUsing XOR smartlySometimes the best solution is not about data structures — it’s about recognizing hidden math patterns.

StringMath TrickASCIIBit ManipulationLeetCodeEasy

LeetCode 2553: Separate the Digits in an Array – Java Solution Explained (2 Easy Approaches)

IntroductionIn coding interviews and competitive programming, many problems test how well you can manipulate numbers and arrays together. One such beginner-friendly problem is LeetCode 2553 – Separate the Digits in an Array.In this problem, we are given an integer array, and we need to separate every digit of every number while maintaining the original order.This problem is excellent for practicing:Array traversalDigit extractionReverse processingArrayList usage in JavaThinking about order preservationProblem Link🔗 ProblemLeetCode 2553: Separate the Digits in an ArrayProblem StatementGiven an array of positive integers nums, return an array containing all digits of each integer in the same order they appear.ExampleInput:nums = [13,25,83,77]Output:[1,3,2,5,8,3,7,7]IntuitionThe main challenge is:Extract digits from each numberPreserve the original left-to-right orderNormally, extracting digits using % 10 gives digits in reverse order.Example:83 → 3 → 8So we need a way to restore the correct order.Approach 1 – Using String ConversionIdeaConvert every number into a string and then traverse each character.This is the simplest and most beginner-friendly approach.AlgorithmTraverse every number in the array.Convert the number into a string.Traverse each character of the string.Convert character back to integer.Store digits into ArrayList.Convert ArrayList to array.Java Code – String Approachclass Solution { public int[] separateDigits(int[] nums) { ArrayList<Integer> list = new ArrayList<>(); for (int num : nums) { String str = String.valueOf(num); for (char ch : str.toCharArray()) { list.add(ch - '0'); } } int[] ans = new int[list.size()]; for (int i = 0; i < list.size(); i++) { ans[i] = list.get(i); } return ans; }}Dry Run (String Approach)Input:nums = [13,25]Step 113 → "13"Digits added:1, 3Step 225 → "25"Digits added:2, 5Final Array:[1,3,2,5]Time Complexity & Space ComplexityTime ComplexityO(N × D)Where:N = number of elementsD = number of digitsSpace ComplexityO(N × D)For storing digits.Approach 2 – Mathematical Digit Extraction (Optimal Without String)This is the approach you implemented in your code.Instead of converting numbers into strings, we extract digits mathematically using:digit = num % 10num = num / 10But digits come in reverse order.To fix this:Traverse the original array from back to frontStore extracted digitsReverse the final resultThis avoids string conversion completely.Intuition Behind Reverse TraversalSuppose:nums = [13,25]If we traverse from the end:25 → 5,213 → 3,1Stored list:[5,2,3,1]Now reverse the list:[1,3,2,5]Correct answer achieved.Java Code – Mathematical Approachclass Solution { public int[] separateDigits(int[] nums) { ArrayList<Integer> list = new ArrayList<>(); for (int i = nums.length - 1; i >= 0; i--) { if (nums[i] < 10) { list.add(nums[i]); } else { int val = nums[i]; while (val != 0) { int digit = val % 10; val = val / 10; list.add(digit); } } } int[] ans = new int[list.size()]; int k = 0; for (int i = list.size() - 1; i >= 0; i--) { ans[k++] = list.get(i); } return ans; }}Dry Run (Mathematical Approach)Input:nums = [13,25,83]Traverse from Back83Digits extracted:3, 8List:[3,8]25Digits extracted:5,2List:[3,8,5,2]13Digits extracted:3,1List:[3,8,5,2,3,1]Reverse Final List[1,3,2,5,8,3]Correct answer.Time Complexity Analysis & Space ComplexityTime ComplexityO(N × D)Because every digit is processed once.Space ComplexityO(N × D)For storing final digits.Which Approach is Better?ApproachAdvantagesDisadvantagesString ConversionEasy to understandUses extra string conversionMathematical ExtractionBetter DSA practiceSlightly harder logicInterview PerspectiveIn interviews:Beginners should first explain the string approach.Then discuss optimization using mathematical extraction.Interviewers like when candidates:Understand digit manipulationThink about order preservationCompare multiple approachesCommon Mistakes1. Forgetting Reverse OrderUsing % 10 extracts digits backward.Example:123 → 3,2,1You must reverse later.2. Not Handling Single Digit NumbersSingle digit numbers should directly be added.3. Character Conversion MistakeWrong:list.add(ch);Correct:list.add(ch - '0');Frequently Asked Questions (FAQs)Q1. Why do digits come in reverse order?Because % 10 always extracts the last digit first.Example:123 % 10 = 3Q2. Can we solve this without ArrayList?Yes, but ArrayList makes dynamic storage easier.Q3. Which approach is more optimal?Both have similar complexity.Mathematical extraction avoids string conversion and is preferred in interviews.Q4. Is this problem important for interviews?Yes. It teaches:Number manipulationOrder handlingArray traversalBasic optimization thinkingConclusionLeetCode 2553 is a simple yet valuable beginner problem for understanding:Digit extractionArray handlingReverse traversalOrder preservationYou learned two approaches:String Conversion ApproachMathematical Digit Extraction ApproachThe mathematical solution is especially useful because it strengthens core DSA concepts and improves problem-solving skills for interviews.If you're preparing for coding interviews in Java, this is a great problem to master before moving to harder digit manipulation questions.

ArrayEasyLeetcodeDigit ExtractionJava

LeetCode 3838: Weighted Word Mapping – Java Solution Explained with Multiple Approaches

IntroductionLeetCode 3838, Weighted Word Mapping, is a straightforward yet interesting problem that combines several fundamental programming concepts:Character mappingHashingModular arithmeticString processingOptimization techniquesAt first glance, the problem appears to be a simple implementation exercise. However, it provides a great opportunity to discuss different approaches and understand how fixed-size alphabets can help us write more efficient code.In this article, we'll explore the problem step-by-step, discuss multiple solutions, perform a dry run, and analyze the complexity of each approach.Problem Link -: Weighted Word MappingProblem StatementYou are given:An array of strings wordsAn integer array weights of length 26Each index in the weights array corresponds to a lowercase English letter.For every word:Calculate the sum of character weights.Take the result modulo 26.Convert the modulo result into a letter using reverse alphabetical order:0 → z1 → y2 → x...25 → aReturn a string formed by concatenating all mapped letters.ExampleInputwords = ["abcd", "def", "xyz"]Output"rij"ExplanationFor the word "abcd":a = 5b = 3c = 12d = 14Total Weight = 3434 % 26 = 88 → rFor "def":14 + 1 + 2 = 1717 % 26 = 1717 → iFor "xyz":7 + 7 + 2 = 1616 % 26 = 1616 → jFinal Answer:"rij"Understanding the Core IdeaThe problem consists of three independent operations:Step 1: Calculate Word WeightFor each word:Weight(word) = Sum of character weightsExample:abca = 5b = 3c = 12Weight = 20Step 2: Apply Modulo 26The problem requires:Weight % 26This guarantees that the result always lies between:0 and 25Step 3: Reverse Alphabet MappingUnlike normal alphabet indexing:0 → a1 → b2 → cthe problem uses:0 → z1 → y2 → x...25 → aThis reverse mapping generates the final encoded character.Approach 1: HashMap-Based SolutionIntuitionCreate:Map 1Character → WeightExample:a → 5b → 3c → 12Map 2Modulo Value → CharacterExample:0 → z1 → y2 → xThen process each word and build the answer.Java Implementationclass Solution { public String mapWordWeights(String[] words, int[] weights) { HashMap<Character,Integer> weightMap = new HashMap<>(); HashMap<Integer,Character> reverseMap = new HashMap<>(); for(int i = 0; i < 26; i++) { char letter = (char)('a' + i); char reverseLetter = (char)('z' - i); weightMap.put(letter, weights[i]); reverseMap.put(i, reverseLetter); } StringBuilder answer = new StringBuilder(); for(String word : words) { int sum = 0; for(char ch : word.toCharArray()) { sum += weightMap.get(ch); } answer.append(reverseMap.get(sum % 26)); } return answer.toString(); }}Approach 2: Optimized Array SolutionObservationThe English alphabet contains only 26 letters.Instead of using HashMaps:weightMap.get(ch)we can directly access:weights[ch - 'a']This eliminates hashing overhead entirely.Why Is This Better?HashMap operations are O(1) on average, but they still involve:Hash computationBucket lookupInternal object handlingArray indexing is faster because it directly accesses memory.Optimized Java Solutionclass Solution { public String mapWordWeights(String[] words, int[] weights) { StringBuilder answer = new StringBuilder(); for(String word : words) { int sum = 0; for(char ch : word.toCharArray()) { sum += weights[ch - 'a']; } int mod = sum % 26; answer.append((char)('z' - mod)); } return answer.toString(); }}Dry RunInputwords = ["abcd"]Assume:a = 7b = 5c = 3d = 4Calculate Weight7 + 5 + 3 + 4 = 19Apply Modulo19 % 26 = 19Reverse Mapping0 → z1 → y2 → x...19 → gResult:"g"Complexity AnalysisHashMap SolutionTime ComplexityO(T)where T is the total number of characters across all words.Space ComplexityO(1)Only fixed-size maps of 26 elements are stored.Optimized Array SolutionTime ComplexityO(T)Space ComplexityO(1)No additional data structures are required.Which Solution Should You Use?ApproachTimeSpaceInterview PreferenceHashMapO(T)O(1)GoodDirect ArrayO(T)O(1)BestBoth solutions are efficient.However, the array-based approach is typically preferred in coding interviews because:Simpler implementationFaster executionLower memory overheadNo unnecessary hashingInterview DiscussionA common follow-up question is:Can we eliminate both HashMaps?Yes.Since:'a' to 'z'are contiguous ASCII characters, we can directly compute:weights[ch - 'a']Similarly:(char)('z' - mod)can generate the reverse mapping without storing another lookup table.This reduces code complexity while maintaining the same asymptotic performance.Key TakeawaysFixed-size alphabets often allow array-based optimizations.HashMaps improve readability but may not always be necessary.Modular arithmetic is useful for reducing values into a bounded range.Character arithmetic can replace lookup tables in many string problems.Always look for opportunities to replace generic data structures with direct indexing when the input domain is small and fixed.ConclusionLeetCode 3838: Weighted Word Mapping is an excellent beginner-friendly problem that demonstrates the practical use of hashing, modular arithmetic, and character manipulation.While a HashMap-based solution is intuitive and easy to understand, recognizing that the alphabet size is fixed allows us to develop a cleaner and more optimized array-based solution.Understanding both approaches not only helps solve this problem efficiently but also strengthens the problem-solving mindset needed for technical interviews and competitive programming.

LeetCodeEasyArrayHashMapStringFrequencyJava

LeetCode 3783 Mirror Distance of an Integer | Java Solution Explained

IntroductionSome problems test complex algorithms, while others focus on fundamental concepts done right.LeetCode 3783 – Mirror Distance of an Integer falls into the second category.This problem is simple yet important because it builds understanding of:Digit manipulationReversing numbersMathematical operationsIn this article, we’ll break down the problem in a clean and intuitive way, along with an optimized Java solution.🔗 Problem LinkLeetCode: Mirror Distance of an IntegerProblem StatementYou are given an integer n.The mirror distance is defined as:| n - reverse(n) |Where:reverse(n) = number formed by reversing digits of n|x| = absolute value👉 Return the mirror distance.ExamplesExample 1Input:n = 25Output:27Explanation:reverse(25) = 52|25 - 52| = 27Example 2Input:n = 10Output:9Explanation:reverse(10) = 1|10 - 1| = 9Example 3Input:n = 7Output:0Key InsightThe problem consists of two simple steps:1. Reverse the number2. Take absolute differenceIntuitionLet’s take an example:n = 120Step 1: Reverse digits120 → 021 → 21👉 Leading zeros are ignored automatically.Step 2: Compute difference|120 - 21| = 99ApproachStep-by-StepExtract digits using % 10Build reversed numberUse Math.abs() for final resultJava Codeclass Solution { // Function to reverse a number public int reverse(int k) { int rev = 0; while (k != 0) { int dig = k % 10; // get last digit k = k / 10; // remove last digit rev = rev * 10 + dig; // build reversed number } return rev; } public int mirrorDistance(int n) { // Calculate mirror distance return Math.abs(n - reverse(n)); }}Dry RunInput:n = 25Execution:Reverse → 52Difference → |25 - 52| = 27Complexity AnalysisTime ComplexityReversing number → O(d)(d = number of digits)👉 Overall: O(log n)Space Complexity👉 O(1) (no extra space used)Why This WorksDigit extraction ensures correct reversalLeading zeros automatically removedAbsolute difference ensures positive resultEdge Cases to ConsiderSingle digit → result = 0Numbers ending with zero (e.g., 10 → 1)Large numbers (up to 10⁹)Key TakeawaysSimple math problems can test core logicDigit manipulation is a must-know skillAlways handle leading zeros carefullyUse built-in functions like Math.abs() effectivelyReal-World RelevanceConcepts used here are helpful in:Number transformationsPalindrome problemsReverse integer problemsMathematical algorithmsConclusionThe Mirror Distance of an Integer problem is a great example of combining basic operations to form a meaningful solution.While simple, it reinforces important programming fundamentals that are widely used in more complex problems.Frequently Asked Questions (FAQs)1. What happens to leading zeros in reverse?They are automatically removed when stored as an integer.2. Can this be solved using strings?Yes, but integer-based approach is more efficient.3. What is the best approach?Using arithmetic operations (% and /) is optimal.

EasyArrayReverse NumberLeetCodeJava

LeetCode 3727 Maximum Alternating Sum of Squares – Java Solution & Explanation

IntroductionLeetCode 3727 – Maximum Alternating Sum of Squares is an array problem where the goal is to rearrange the elements to obtain the largest possible alternating score.At first, the formula looks straightforward:score = arr[0]2 - arr[1]2 + arr[2]2 - arr[3]2 + ...However, the challenge is deciding which squared values should occupy the positive positions and which should occupy the negative positions.A useful observation makes the problem easier: the values added to the score should be as large as possible, while the values subtracted should be as small as possible.This solution uses sorting to arrange the squared values, then alternates between taking the largest remaining value for a positive position and the smallest remaining value for a negative position.There is also a small debugging lesson from the submission process: a System.out.println() statement that appears harmless during development can add enough output overhead to contribute to a Time Limit Exceeded (TLE) result.Problem StatementProblem Link-: Maximum Alternating Sum of SquaresGiven an integer array nums, the elements can be rearranged in any order.The alternating score is defined as:score = arr[0]2 - arr[1]2 + arr[2]2 - arr[3]2 + ...Return the maximum possible alternating score after rearranging the array.Example 1Input: nums = [1, 2, 3]Output: 12One valid rearrangement is:[2, 1, 3]Its score is:2^2-1^2+3^2=4-1+9=12Example 2Input: nums = [1, -1, 2, -2, 3, -3]Output: 16One rearrangement that achieves the maximum is:[-3, -1, -2, 1, 3, 2]The score is:9-1+4-1+9-4=16Notice that negative numbers do not remain negative after squaring. For example, ((-3)^2=9), just like (3^2=9).Understanding the Greedy IdeaBefore looking at the code, consider the sign of each position in the alternating sum.PositionContributionIndex 0Add the squareIndex 1Subtract the squareIndex 2Add the squareIndex 3Subtract the squareIndex 4Add the squareThe even indices contribute positively, and the odd indices contribute negatively.To maximize the total, the positive positions should receive large squared values, while the negative positions should receive small squared values.For example, suppose the squared values are:[1, 4, 9]A good arrangement is:[9, 1, 4]The alternating score becomes:9-1+4=12This is better than:1-4+9=6The sorting step makes the largest and smallest remaining values easy to access. Two pointers can then select them in the required order.Java SolutionThe following implementation follows the submitted approach: square the elements, sort them, and build a new array by alternating between the largest and smallest remaining values.class Solution { public long maxAlternatingSum(int[] nums) { for (int i = 0; i < nums.length; i++) { nums[i] = nums[i] * nums[i]; } Arrays.sort(nums); int[] n = new int[nums.length]; int l = 0; int h = nums.length - 1; int v = 0; while (v < nums.length && l < h) { if (v % 2 == 0) { n[v] = nums[h]; h--; v++; } else { n[v] = nums[l]; l++; v++; } } if (h - l != 1) { n[v] = nums[l]; } long sum = 0; for (int i = 0; i < nums.length; i++) { if (i % 2 == 0) { sum += n[i]; } else { sum -= n[i]; } // System.out.println(n[i]); } return sum; }}Step-by-Step Explanation1. Square every elementfor (int i = 0; i < nums.length; i++) { nums[i] = nums[i] * nums[i];}The score uses squares, so each element is converted into its squared value.For example:Original: [1, -1, 2, -2, 3, -3]Squared: [1, 1, 4, 4, 9, 9]This also explains why the original signs no longer affect the ordering after squaring.2. Sort the squared valuesArrays.sort(nums);After sorting:[1, 1, 4, 4, 9, 9]Now the smallest value is at index 0, and the largest is at the last index.3. Use two pointersint l = 0;int h = nums.length - 1;l points to the smallest remaining value.h points to the largest remaining value.v represents the position currently being filled in the new array.At even positions, the code selects the largest remaining value:n[v] = nums[h];h--;At odd positions, it selects the smallest remaining value:n[v] = nums[l];l++;This creates the desired pattern of large positive contributions and small negative contributions.4. Calculate the alternating scoreif (i % 2 == 0) { sum += n[i];} else { sum -= n[i];}The final traversal adds values at even indices and subtracts values at odd indices.The result is stored in a long, which is important because the sum of squared values can exceed the range of a 32-bit integer.Dry RunConsider:nums = [1, 2, 3]After squaring and sorting:[1, 4, 9]Initially:l = 0h = 2v = 0The two pointers select values as follows:StepPositionSelectionValue10Largest remaining921Smallest remaining132Remaining value4The new array becomes:[9, 1, 4]Now calculate the alternating score:IndexValueOperationRunning Sum09+9911-1824+412Therefore:Output: 12The largest squared value contributes positively, while the smallest is subtracted.A Real Debugging Lesson: Why Did Removing System.out.println() Help?While testing a solution, it is common to add a print statement to inspect intermediate values:// System.out.println(n[i]);In this submission, the statement was inside the loop that processes every element.The interesting part is that the solution received a Time Limit Exceeded result while the print statement was active, but was accepted after the statement was commented out.Why can that happen?Console output has a costPrinting is not the same as assigning a value to a variable. A call to System.out.println() involves output handling, and online judges may capture or process that output.When the statement executes repeatedly, the accumulated overhead can become significant.For an array with many elements, a loop such as:for (int i = 0; i < nums.length; i++) { // Process the current element System.out.println(n[i]);}produces up to (n) lines of output.That work is unnecessary when the final submission only needs to return the answer.Why commenting it out can matterRemoving the print statement eliminates the repeated console-output operations. This can make a submission faster, particularly when the execution environment imposes overhead on captured output.However, a TLE is not automatically caused by printing. An inefficient algorithm, repeated string operations, or other unnecessary work can also cause it.The practical lesson: use print statements while debugging, but remove them before submitting unless the problem explicitly requires output through standard output.This is a useful reminder that competitive programming performance depends not only on the algorithm but also on the extra work performed inside its loops.Complexity AnalysisLet (n) be the length of nums.Time complexity: (O(nlog n))Squaring the elements takes (O(n)).Sorting takes (O(n\log n)).Rearranging the values takes (O(n)).Calculating the alternating sum takes (O(n)).Sorting dominates the total time complexity.Auxiliary space: (O(n))The implementation creates a new array of length (n). The sorting implementation may also use additional internal space.An Important Implementation NoteThe submitted solution works through a somewhat complicated final-element condition:if (h - l != 1) { n[v] = nums[l];}This handles the remaining element for certain pointer configurations, but the condition is harder to reason about than necessary.A cleaner implementation can avoid the extra array and special condition by accumulating the score directly while selecting values. It is also important to square into a long if the input constraints might permit values whose squares exceed the int range.For this problem's stated bounds, the square of an individual value fits in an int, but using long for the score protects the accumulated result.The broader lesson is to keep pointer conditions simple and test arrays of length one, odd lengths, and even lengths when implementing two-pointer rearrangements.Interview TakeawayFor array problems involving an alternating sum, identify which positions contribute positively and which contribute negatively before deciding how to sort the data.The key questions are:Which values should be maximized?Which values should be minimized?Can sorting make those values easy to select?Can two pointers build the required arrangement without unnecessary operations?This reasoning connects the problem to a broader set of greedy and sorting questions in which the order of elements determines the final score.ConclusionLeetCode 3727 – Maximum Alternating Sum of Squares combines array manipulation, sorting, two pointers, and greedy reasoning.The central idea is to maximize the values added to the score and minimize the values subtracted from it. Squaring the elements first makes the problem about arranging non-negative values, and sorting allows the largest and smallest remaining values to be selected efficiently.The debugging experience adds one more practical lesson: remove unnecessary console output from performance-sensitive loops before submitting a solution. A small development convenience can create measurable overhead, even when the underlying algorithm is sound.Together, the greedy observation and the debugging lesson make this problem useful both for algorithm practice and for building better submission habits.

LeetCodeJavaArraysSortingMedium

Max Consecutive Ones III – Sliding Window with Limited Flips

IntroductionLeetCode 1004: Max Consecutive Ones III is a classic sliding window problem that challenges your understanding of arrays, window manipulation, and frequency counting.The goal is to find the longest subarray of consecutive 1's in a binary array if you are allowed to flip at most K zeros to 1’s.This problem is an excellent example of transforming a brute-force solution into a linear-time efficient approach using the sliding window pattern.If you’d like to try solving the problem first, you can attempt it here: Try the problem on LeetCode: https://leetcode.com/problems/max-consecutive-ones-iii/Problem UnderstandingYou are given:A binary array nums containing only 0's and 1'sAn integer k representing the maximum number of zeros you can flipYou need to return the length of the longest contiguous subarray of 1's after flipping at most k zeros.Examples:Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2Output: 6Explanation: Flip two zeros to get [1,1,1,0,0,1,1,1,1,1,1].Longest consecutive ones = 6.Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3Output: 10Explanation: Flip three zeros to get longest consecutive ones of length 10.A naive approach would check every possible subarray, flip zeros, and count consecutive ones:Time Complexity: O(n²) → too slow for large arraysInefficient for constraints up to 10⁵ elementsKey Idea: Sliding Window with Zero CountInstead of brute-force, notice that:We only care about how many zeros are in the current windowWe can maintain a sliding window [i, j]Keep a counter z for zeros in the windowExpand the window by moving jIf z exceeds k, shrink the window from the left by moving i and decrementing z for each zero removedIntuition:The window always contains at most k zerosThe length of the window gives the maximum consecutive ones achievable with flipsThis allows linear traversal of the array with O(1) space, making it optimal.Approach (Step-by-Step)Initialize pointers: i = 0, j = 0Initialize z = 0 (zeros count in current window) and co = 0 (max length)Iterate j from 0 to nums.length - 1:If nums[j] == 0, increment zCheck z:If z <= k: window is valid → update co = max(co, j - i + 1)Else: shrink window by moving i until z <= k, decrement z for zeros leaving windowContinue expanding window with jReturn co as the maximum consecutive onesOptimization:Only need one variable for zeros countAvoids recomputing sums or scanning subarrays repeatedlyImplementation (Java)class Solution { public int longestOnes(int[] nums, int k) { int co = 0; // maximum length of valid window int i = 0, j = 0; // window pointers int z = 0; // count of zeros in current window while (j < nums.length) { if (nums[j] == 0) { z++; // increment zeros count } if (z <= k) { co = Math.max(co, j - i + 1); // valid window j++; } else { // shrink window until zeros <= k while (z > k) { if (nums[i] == 0) { z--; } i++; } co = Math.max(co, j - i + 1); j++; } } return co; }}Dry Run ExampleInput:nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2Execution:Window [i, j]Zeros zValid?Max length co[0,0] → [1]0Yes1[0,2] → [1,1,1]0Yes3[0,3] → [1,1,1,0]1Yes4[0,4] → [1,1,1,0,0]2Yes5[0,5] → [1,1,1,0,0,0]3No → shrink i5[3,8] → [0,0,1,1,1,1]2Yes6Output:6Complexity AnalysisTime Complexity: O(n) → Each element is visited at most twice (once when j moves, once when i moves)Space Complexity: O(1) → Only counters and pointers usedEdge Cases Consideredk = 0 → cannot flip any zeros, just count consecutive onesArray with all 1’s → return full lengthArray with all 0’s → return min(k, length)Single element arrays → works correctlySliding Window Pattern ImportanceThis problem is a perfect example of the sliding window pattern:Use a window to track a condition (max zeros allowed)Expand and shrink dynamically based on constraintsEfficiently computes maximum/minimum contiguous subarray lengthsIt also demonstrates counting with limited violations – a key interview concept.ConclusionBy tracking zeros with a sliding window, we convert a naive O(n²) problem into O(n) linear time.Understanding this pattern allows you to solve:Max consecutive ones/zeros problemsLongest substring/subarray with constraintsSubarray problems with limited replacements or violationsOnce mastered, this approach applies to many binary array and string problems efficiently.

SlidingWindowBinaryArrayLeetCodeMedium