Posts

Showing posts from July, 2022

Leetcode Longest Substring Without Repeating Characters

Question Given a string s, find the length of the longest substring without repeating characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring. Constraints: 0 Initial thought process let us consider a string ABCDAEJKL. So my initial thought process was I started counting with a letter and as soon as I found it has been repeated I used to reset the counter. So my answer for above string would be 5 but it was an obvious mistake as I was skipping the characters after first A, the solution to this was to maintain a map and position of every character and as a character is repea...

LeetCode 3Sum

Question Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Brute force We can run 3 loops to check each possible triplets, we also need to eliminate the duplicates from both sides. this method will work but will work but will give time limit exceed after time constraints. To do this in given time limit we need to sort the array first and Create a loop that fixes the left most integer. This reduces the problem to 2sum for remaining array. For each loop iteration where duplicates are skipped, we need to do a left/right iteration using while loop. my code:

New Start onwards: Learning Bitset in C++

 Bitset This is a C++ STL library that can be used as bool and all bitwise operations can be performed on it. It is declared as bitset<size> name; here size is the number of bits you want. For example, if size=10 it will act as a bool array of size 10.  you can set ith bit by using "name.set(i);" but note the bit indexing starts from the right side and from 0. If our bit set is for example bitset<12>name; and we used name.set(5) the result will be 000000100000. also, there's an interesting thing  here in the above code, you will see in the val bitset we set 1,5 and 8th (indexes) and in diff bitset we perform an operation for each i which is true, diff|= (val>>i) or (diff =diff||(val>>i)) so we perform 'or'operation of diff using val.  So what happens is let's say we have initial val 0010001000 where bit 3 and bit 7 is 1 or set. if we perform operation val>>3 we will get 0000001001 we get bit 0 and bit 4 set. We can say that this s...