It's the Xinrui Ma

Blog

Tag: LeetCode

Remove duplicate char in TypeScript

Posted by in LeetCode on

Question: How will you remove duplicate characters from a sting?

You: This is very similar to first non repeating char. You will asks similar question. Is it case sensitive.

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

Algorithm:

By using HashSet as a sliding window, checking if a character in the current can be done in O(1)O(1).

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices, i.e. [i, j)[i,j) (left-closed, right-open). A sliding window is a window “slides” its two boundaries to the certain direction. For example, if we slide [i, j)[i,j) to the right by 11 element, then it becomes [i+1, j+1)[i+1,j+1) (left-closed, right-open).

Back to our problem. We use HashSet to store the characters in current window [i, j)[i,j) (j = ij=i initially). Then we slide the index jj to the right. If it is not in the HashSet, we slide jj further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index ii. If we do this for all ii, we get our answer.

The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.


Key idea: If we find str.charAt(j) already exists in map at position k, we change our i to k + 1.

Solution:

260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Answer:

Take a look at my previous post: http://maxinrui.com/index.php/2016/09/27/136-single-number-leetcode/

“Two same integers after XOR operation, the value is 0, and 0 XOR any integer is the integer itself”

Assume there are b and c that only appear once in the array, so, if we follow the same steps, perform XOR operation on each array elements, we could end up getting b ^ c;

What could b ^ c do for us?

It would be much simpler if the array can be split into two arrays that each only contain b or c, then we just do a XOR to all elements in each array, we could get the b and c.

That’s what b ^ c can do for us.

As we know, there must be a Kth bit of b and c that is different, otherwise they will be the same. Find the Kth bit that is different, we can use that to split the array into two arrays.

137. Single Number II LeetCode

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Answer:

So when it comes with word like that “without using extra memory”, I will think of bit manipulation.

Since integer is 32 bits, and integers appears exactly three times except for one, so on the bit level, every bit of will be either 0 or 1, for all integers appears three times,the sum of them on the bit level will be a multiple of 3, after we do a mod 3, the result will be 0. so the only one that will not be 0 after mod 3, is the one that appear only once.

136. Single Number — LeetCode

Given an array of integers, every element appears twice except for one. Find that single one.

Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Thought:

I can do this in Hash table, but that doesn’t meet the requirement ” implement it without using extra memory”

So, Hash table is not a best answer.

I read that operation about bit manipulation last night and that is a fact I found:

“Two same integers after XOR operation, the value is 0, and 0 XOR any integer is the integer itself”

So the condition is that “every element appears twice except for one”

So just do XOR for every element in the array, the final result is the integer we are looking for.