Hashmap

Problem Overview We are given an array of strings strs Our goal is to group the anagrams together and return an array of array of strings All strings are in lowercase English letters Leetcode - Group Anagrams Example Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]] nat and tan are anagrams ate, eat and tea are anagrams There is no anagram for bat in the array If you dont know how to find anagrams then refer this Valid Anagrams ...

Problem Overview We are given s and t of length m and n respectively We need to check if t is a valid anagram of s or not. All characters will be in lowercase. Note — An anagram is a word or phrase that is built by rearranging the characters of another word in a different order to form a new word. LeetCode - Valid Anagram Example Input: s = "anagram", t = "nagaram" Output: true Input: s = "rat", t = "car" Output: false Brute Force Intuition If t and s are not of the same size, then they cannot be valid anagrams. If all the characters present in s are present in t with the same frequency, then it is a valid anagram. Use an array to store the frequency of characters from s. Then iterate over t and decrease the frequency. Finally iterate over the array — if anything other than 0 is present, then it is invalid. Code class Solution { public: bool isAnagram(string s, string t) { if(s.size() != t.size()) return false; vector<int> freq = vector<int>(26, 0); for(auto it: t){ freq[it-'a']++; } for(auto it: s){ freq[it-'a']--; } for(auto it: freq){ if(it != 0) return false; } return true; } }; Time & Space Complexity Time - O(n) Space - O(26) → O(1) Optimization Intuition Instead of checking validity in a separate loop, we can decrease the frequency and check it in the same loop. To further optimize, we can use a fixed-size array instead of a vector. Code class Solution { public: bool isAnagram(string s, string t) { if(s.size() != t.size()) return false; int freq[26] = {0}; for(char c : s) freq[c-'a']++; for(char c : t) if(--freq[c-'a'] < 0) return false; return true; } }; Time & Space Complexity Time - O(n) Space - O(26) → O(1) Key Takeaways You need to understand what an anagram is before solving the problem. Observe and try to reduce unnecessary iterations if possible.

Problem Overview Given strings s and t of length m and n respectively, return the minimum length substring of s such that every character in t is present in the substring. The substring can contain duplicate characters. LeetCode - Rotate Image Example: Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" BANC is the minimum window containing all characters from t. ...

Problem Overview We are given a string s. Our goal is to find the longest substring that does not contain repeating characters. In other words, the length of the substring should equal the number of unique characters in it. If found → return the length, otherwise → return 0. There can be multiple valid substring of length LeetCode - Longest Substring Without Repeating Characters A substring is continous part of string. The string itself is a valid substring. ...

Problem Overview We are given an array of integers nums and an integer target. Our Goal is to find two distinct integers from the array, such that their sum is equal to the target and return their indices. Constraints: The array contains at least 2 elements. Exactly one valid solution exists. The goal is to design a solution with O(n) time complexity. Lets Fund out how i approached this problem and what were my thoughts while solving this. ...