Blind-75

Problem Overview We are given a string s. The string consists of all printable ASCII characters. Goal is to check if the string is a palindrome — but first we need to remove non-alphanumeric characters, then check. A palindrome is a word or sentence if that reads the same backwards as forewords LeetCode - Valid Palindrome Example Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome. Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome. ...

Problem overview We are given a string s containing only the characters '(', ')', '{', '}', '[', and ']'. We need to determine if the input string is valid or not. A string is valid if: Open brackets must be closed by the same type of bracket. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type. LeetCode - Valid Parentheses ...

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 You’re given a string s (uppercase letters only) and an integer k. You can replace any character in the string up to k times. Return the length of the longest substring containing the same letter after performing those replacements. Brute Force Intuition The idea is straightforward — generate every possible substring, track the frequency of each character inside it, and check if the window is “valid.” Try all possible substrings with two nested loops Track character frequency within the current substring Track maxFreq — the count of the most frequent character If len - maxFreq <= k, the window is valid — update the result How this works, we have the maxFreq of that substring if we subract it from the len then we got len of other chars. The string is only valid if the no of conversion we have to make is less than k that is length - maxFreq; ...

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 the head of a singly linked list. We are given a node index n from the end. The goal is to remove the nth node from the end of the list. Constraints We have to do this in a single pass. Leetcode - Linked List Cycle Brute Force Approach Intuition We use a vector to keep track of the nodes and their indices. Once the traversal is finished, we calculate the node index from the start. Once we get that index, we remove that node. Code class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { vector<ListNode*> arr; ListNode* curr = head; while (curr) { arr.push_back(curr); curr = curr->next; } int nodeFromStart = arr.size() - n; if (nodeFromStart == 0) return head->next; if (nodeFromStart < arr.size()) arr[nodeFromStart - 1]->next = arr[nodeFromStart]->next; return head; } }; Why This Fails It usegs extra space O(n). The problem requires a constant space solution. Time and Space Complexity Time: O(n) Space: O(n) Optimal Approach We maintain two pointers similar to Floyd’s Tortoise and Hare technique. ...

Problem Overview We are given the heads of two singly linked lists. Both the linked lists are sorted in ascending order. Our goal is to merge the two lists into one sorted list and return the head. Leetcode - Linked List Cycle Example Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4] Brute Force Intuition We can simply traverse each list and push all values into a vector. Then we sort the vector. While iterating through the vector, we create a new linked list. Code class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { vector<int> values; while (list1) { values.push_back(list1->val); list1 = list1->next; } while (list2) { values.push_back(list2->val); list2 = list2->next; } sort(values.begin(), values.end()); ListNode dummy(0); ListNode* tail = &dummy; for (int val : values) { tail->next = new ListNode(val); tail = tail->next; } return dummy.next; } }; Why This Fails The lists were already sorted, and we are not taking advantage of that. It uses extra memory. Sorting adds unnecessary overhead. Time and Space Complexity Time: O(n log n) Space: O(n) Optimal Solution Instead of collecting all values, we directly compare nodes from both lists and attach the smaller one. ...

Problem Overview We are given the head of a singly linked list. We need to detect if a cycle is present in the list or not. Follow-up: Solve this in constant space. Leetcode - Linked List Cycle Example 3 → 2 → 0 → 4 ↑ ↓ └─────┘ As the last node 4 is linked back to 0, a cycle is present. Brute Force Intuition The idea is to store each node in a map. While iterating, if we encounter the same node again, there is a loop. ...