Longest_Sub_String_ No_Repeat_Characters

Let me continue my work here.

Longest substring without Repeating Characters

Problem Statement:

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

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", which the length is 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

Solution One: Brute Force

Just a simple and brutal solution. First we iterate all possible sub strings and then we check whether characters in this string are all unique. Since we have to iterate the string from an outer loop and inner loop, the time complexity for these loops are:

n-1 + n – 2 + …. + 1 = (n – 1) * n / 2

which is O(n^2), however, for each sub-string we have extracted, we need to check whether it has identical character, which is O(n). Sum it together, we get the O(n^3).

The space complexity depends on the characters in the string. If all of the characters are unique, and our set will never contain identical characters, then the maximum size of our unordered_set is max number of our characters, let’s say m. However, it’s highly possible that our string is less than m, so the space complexity should be O(min(m,n)).

Time complexity: O(n^3)

Space complexity: O(min(m,n))

	class Solution {
	public:
	bool isAllUnique(string &s, int start, int end)
	{
	unordered_set<char> hash;
	for(int i = start; i <= end; i++)
	{
	if(hash.find(s[i]) != hash.end())
	return false;
	hash.insert(s[i]);
	}
	return true;
	}
	int lengthOfLongestSubstring(string s) {
	int len = s.size();
	int maxLen = s.empty()? 0 : 1;
	for(int i = 0; i < len; i++)
	{
	for(int j = i + 1; j< len; j++)
	{
	if(isAllUnique(s, i, j))
	maxLen = max(j – i + 1, maxLen);
	}
	}
	return maxLen;
	}
	};

view raw

Longest_Sub_string_without_Repeat_Characters_BruteForce.cpp

hosted with ❤ by GitHub

Solution Two: Sliding

The brute force algorithm is extremely slow. How can we do better?

Let’s observe what is going on when we run the loop… When the loop begins:

j = 1, check string[0:1], whether the sub-string is unique;

j = 2, check string[0:2], whether the sub-string is unique;

j = 3, check string[0:3], whether the sub-string is unique;

…

Can you see it, we have done a lot of repetitive job. If we already know that string[0:3] contains an identical character, we do not need to check string[0:3] anymore in string[0:4], we just need to check whether string[3] is in the string[0:3]… if it is, then string[3] is not an unique character, which means that string[0:4] must contain identical characters, so all the following string[0:n] must contain identical characters, we do not need to increase j any more, we just directly increase i; if it is not, then j moves forward, and put string[3] in the set.

slide

Another potential improvement is, when we find that a sub string contains an identical character, we do not need to increase i one by one. We can just make i jump directly to the next position of first identical character, then the loop continues.

Since we only iterate j in the loop and make i jump from point to point, so the whole running time should be O(n). The space complexity should be the same as the solution one (we still need to maintain the hash table).

Time complexity: O(n)

Space complexity: O(min(m,n))

	class Solution {
	public:
	int lengthOfLongestSubstring(string s) {
	unordered_map<char, int> set;
	int n = s.size();
	int i=0, j=0, maxLength = 0;
	while(i<n&&j<n)
	{
	if(set.find(s[j])!=set.end())
	{
	i = max(i,set[s[j]]);
	set.erase(s[j]);
	}
	else
	{
	set[s[j]] = j + 1;
	maxLength = max(maxLength, j-i+1);
	j++;
	}
	}
	return maxLength;
	}
	};

view raw

Longest_Sub_String_without_Repeat_Characters_Sliding.cpp

hosted with ❤ by GitHub

Solution Three: Character Dictionary

This is a tricky solution. Instead of tracking each character in the string, we first build a dictionary array which contains all the possible characters. When we iterate our string, we put the index of each character to the dictionary and track our first index of a unique sub string using a variable named as start, then we increase our iteration and find the same character as the first one of this unique sub string , we can calculate the length of this unique sub string:

i – start; // start is initially set as -1;

We only update our start variable when we encounter an identical character, and we set start variable be the index of that first identical character. After that, we calculate the length of this sub string and compare it with the max length.

The time complexity of this solution is O(n), since we iterate the string once. While the space complexity is equal to character types. We have to use the same number of space as numbers of character types. It might be more useful for English Ascii characters. Since it is very powerful when we want to check a very long string which contains only Ascii characters.

Time complexity: O(n)

Space complexity: O(m) m is the number of character types.

	class Solution {
	public:
	int lengthOfLongestSubstring(string s) {
	vector<int> dict(256,-1);
	int maxLength = 0, start = –1;
	for(int i =0; i<s.size(); i++)
	{
	if(dict[s[i]] > start)
	start = dict[s[i]];
	dict[s[i]] = i;
	maxLength = max(maxLength, i – start);
	}
	return maxLength;
	}
	};

view raw

Longest_Sub_String_without_Repeat_Characters_Dictionary.cpp

hosted with ❤ by GitHub

That’s all for this article…

Longest substring without Repeating Characters

共享此文章：

Like this:

Related

Leave a Reply Cancel reply