Search Blogs

Showing results for "ASCII"

Found 5 results

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

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

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

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 17: Letter Combinations of a Phone Number — Java Solution and Backtracking Explained

IntroductionHave you ever wondered how a phone number can represent multiple possible words? On a traditional telephone keypad, each digit from 2 to 9 is associated with three or four letters. For example, 2 represents a, b, and c, while 3 represents d, e, and f.Now imagine entering the digits "23". For every letter represented by 2, we can combine it with every letter represented by 3. This produces nine possible combinations, including "ad", "ae", "af", "bd", and "cf".This is the central idea behind LeetCode 17: Letter Combinations of a Phone Number. The challenge is to generate every possible combination without missing any valid result.In this article, we will explore a recursive Java solution, understand how the keypad mapping is built, and trace how the recursive calls generate the final list.Problem link: LeetCode 17 — Letter Combinations of a Phone NumberUnderstanding the ProblemYou are given a string digits containing numbers from 2 to 9. Each digit corresponds to a group of letters on a telephone keypad.Your task is to return all possible strings that can be formed by choosing exactly one letter for each digit.For example, if the input is "23":Digit 2 can contribute a, b, or c.Digit 3 can contribute d, e, or f.Each letter selected from the first group must be paired with every letter in the second group.The resulting combinations are:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]The order of the returned combinations does not matter.One important detail is that the digits 0 and 1 are not included in the input constraints because they do not map to letters in this problem.Approach: Recursion with Phone Keypad MappingThe key observation is that each digit represents a choice, and recursion explores every available choice at the current position.For example, when processing "23", we first select a letter from digit 2. After that, we move to digit 3 and try all its letters. Once we have selected one letter for each digit, we have completed a valid combination.Our solution uses three main components.1. Build the digit-to-letter mappingWe create a list of character lists called arr.Each position represents a digit, and the corresponding list contains its letters. For instance:arr.get(2) contains a, b, c.arr.get(3) contains d, e, f.arr.get(7) contains p, q, r, s.arr.get(9) contains w, x, y, z.We begin with two empty lists at indices 0 and 1, so the mapping for a digit can be accessed directly using its numeric value.The variable charnum starts at 97, the ASCII value of lowercase a. We convert consecutive numeric values into characters and advance the counter by three or four letters, depending on the digit.This lets us construct the entire keypad mapping programmatically rather than writing each group manually.2. Recursively build each combinationThe helper method sol() receives four parameters:arr: the phone keypad mapping.ind: the current position in the input string.dig: the original digit string.sb: the combination constructed so far, represented as a string.At each recursive call, we examine the current digit and iterate over its available letters.For every letter, we make another recursive call with that letter appended to the current combination. This continues until every digit has contributed one letter.3. Stop when a complete combination is formedThe base condition is:if (sb.length() == dig.length())When the constructed string has the same length as the input digit string, we have selected one letter for every digit. We add that combination to the result list and return from the current call.The recursive process then continues exploring the remaining choices.This is the essential stopping condition that prevents the recursion from continuing beyond the number of input digits.Java SolutionHere is the recursive solution, preserving your approach while making two small improvements:Use a StringBuilder when adding a letter instead of repeatedly creating intermediate strings.Handle an empty input and keep the result list local to the method, so repeated calls do not accidentally reuse results from a previous invocation.import java.util.ArrayList;import java.util.List;class Solution {public void sol(List<List<Character>> arr,int ind,String digits,StringBuilder sb,List<String> lis) {if (ind == digits.length()) {lis.add(sb.toString());return;}int digit = digits.charAt(ind) - '0';for (char ch : arr.get(digit)) {sb.append(ch);sol(arr, ind + 1, digits, sb, lis);sb.deleteCharAt(sb.length() - 1);}}public List<String> letterCombinations(String digits) {List<String> lis = new ArrayList<>();if (digits.isEmpty()) {return lis;}List<List<Character>> arr = new ArrayList<>();arr.add(new ArrayList<>());arr.add(new ArrayList<>());int charnum = 97;for (int i = 0; i < 8; i++) {List<Character> li = new ArrayList<>();int count = (i == 5 || i == 7) ? 4 : 3;for (int j = 0; j < count; j++) {li.add((char) (charnum + j));}arr.add(li);charnum += count;}sol(arr, 0, digits, new StringBuilder(), lis);return lis;}}Why use StringBuilder and remove the last character?Your original code uses sb + arr.get(...).get(i) to create a new string for each recursive call. This is valid Java, but repeated string concatenation creates additional string objects.The improved version modifies a single StringBuilder:append(ch) adds the chosen letter.The recursive call explores the combinations that begin with that letter.deleteCharAt(sb.length() - 1) removes the letter after returning, allowing the next letter to be tried.This pattern is called backtracking. We make a choice, explore its consequences, and undo the choice before exploring another branch.It is especially useful when generating permutations, combinations, subsets, and other possible arrangements.Dry Run: digits = "23"Let's trace the recursion to see exactly how the combinations are generated.Initially, the current string is empty, and the current index is 0.Current choiceNext digit choiceCombination producedadadaeaeafafbdbdbebebfbfcdcdcececfcfThe process follows this sequence:Select a from digit 2.Explore all choices from digit 3, producing ad, ae, and af.Return to the first digit and replace a with b.Explore digit 3 again, producing bd, be, and bf.Repeat with c, producing cd, ce, and cf.The final result contains nine combinations.Why nine? The first digit has three choices, and the second digit also has three choices. Therefore, the total number of combinations is 3 × 3 = 9.Complexity AnalysisLet n be the length of the input string, and let R be the total number of generated combinations.Every digit has either three or four possible letters. The maximum number of combinations is therefore 4^n.Time complexity: O(n × R)There are R complete combinations, each containing n characters. Constructing and storing all these strings requires O(n × R) total time. Since R can be as large as 4^n, the worst-case time complexity is O(n × 4^n).Auxiliary space complexity: O(n)The recursion depth is at most n, and the StringBuilder holds at most n characters. The keypad mapping contains a fixed number of letters, so its space usage is constant with respect to the input length.Output space: O(n × R)The result list stores R strings, each of length n. This output memory is separate from the auxiliary space used by the algorithm.Because the constraints limit the input to at most four digits, the number of generated combinations remains small.Common Mistakes to Avoid1. Forgetting to advance to the next digitEvery recursive call must process the next position. If the index is not incremented, recursion will keep processing the same digit.2. Using an incorrect base conditionThe recursion should stop after processing all digits. Checking whether the current string has the same length as the input works, but checking ind == digits.length() directly makes the relationship between the index and the stopping condition clearer.3. Forgetting to undo a choiceWhen using a shared StringBuilder, remember to remove the character after the recursive call. Otherwise, letters from one branch may incorrectly carry over into another.4. Reusing a result list across separate callsIn your original implementation, lis is a class-level field. If the same Solution instance is used for multiple calls, previous results can remain in the list. Creating the result list inside letterCombinations() avoids this issue.5. Ignoring empty inputThe provided constraints guarantee at least one digit, but returning an empty list for an empty input is a useful defensive behavior. It also avoids accidentally treating the empty string as a valid result.Interview Tip: Recognize the Backtracking PatternWhenever a problem asks you to generate every possible arrangement from several groups of choices, consider recursion or backtracking.A useful way to design the solution is to ask:What choices are available at the current position?What state should be passed to the next recursive call?When is a complete answer formed?What needs to be undone before exploring the next choice?For this problem, the choices are the letters associated with the current digit, the state is the current combination and digit index, and a complete answer is reached after processing all digits.The same reasoning can help with problems such as generating subsets, permutations, combination sums, and other recursive search problems.ConclusionLeetCode 17, Letter Combinations of a Phone Number, is a useful introduction to recursive backtracking in Java. The phone keypad gives us a set of choices for every digit, and recursion explores every possible sequence of those choices.The most important part is not the keypad mapping itself. It is learning how to explore one choice completely, return to the previous state, and then try the next choice without mixing results between branches.Once this pattern becomes familiar, many combination-generation problems become easier to approach and explain in coding interviews.Key takeaway: Build the keypad mapping, choose one letter per digit, stop when every digit has been processed, and backtrack to explore the remaining possibilities.

LeetCodeJavaBacktrackingRecursionStringArrayListDSAMediumCombination