Search Blogs

Showing results for "ASCII"

Found 4 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