Longest Substring Without Repeat Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/longest-substring-without-repeat

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

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

Naive Approach

We can simply check all the substrings if they contain unique elements or not and return the length of the longest substring having unique elements. To check if all the elements in a substring are unique hashmap can be used.

Analysis

• Time Complexity: O(n3)
• Auxiliary Space Complexity: O(n)

Implementation

C++

int longestSubstringWithoutRepeat(string s) {
    int n = s.size();
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			int flag = 1;
			map<int, int> uniqueCharacterCount;
			for (int index = i; index <= j; index++) {
				if (uniqueCharacterCount[s[index] - 'a'] == 1) {
					flag = 0;
					break;
				}
				uniqueCharacterCount[s[index] - 'a'] = 1;
			}
			if (flag == 1) {
				ans = max (ans, j - i + 1);
			}
		}
	}
	return ans;
}

Java

class Solution {
	int longestSubstringWithoutRepeat(String s) {
	    int n = s.length();
		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				int flag = 1;
				HashMap<Integer, Integer> uniqueCharacterCount = new HashMap<Integer, Integer> ();
				for (int index = i; index <= j; index++) {
					if (uniqueCharacterCount.get(s.charAt(index) - 'a') != null) {
						flag = 0;
						break;
					}
					uniqueCharacterCount.put(s.charAt(index) - 'a', 1);
				}
				if (flag == 1) {
					ans = Math.max (ans, j - i + 1);
				}
			}
		}
		return ans;
	}
}

Optimal Approach

The problem can be solved efficiently by storing the last index of every character found while traversing the array. The idea is if we encounter an element that has occurrence before, then the current unique substring must have starting point after the previous occurrence of the current character.

• Initialize an array to store the previous occurrence of all the characters.
• Initialize the start point to 0.
• Traverse the array fromi = 0 to i = n and for every character check the index of the previous occurrence of the character. If the previous occurrence is greater than or equal to start, then update start to previous occurrence + 1.
• Store the current index of the character in the array as the previous occurrence.
• Update the maximum value of longest substring to max(longest substring, i - start + 1).

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)
  Constant space since we are taking a single array of length 26.

Implementation

C++

int longestSubstringWithoutRepeat(string s) {
    int n = s.size();
	int longestSubstring = 0;
	vector<int> previousIndex (26, - 1);
	int start = 0;
	for (int i = 0; i < n; i++) {
		if (previousIndex[s[i] - 'a'] >= start) {
			start = previousIndex[s[i] - 'a'] + 1;
		}
		previousIndex[s[i] - 'a'] = i;
		longestSubstring = max(longestSubstring, i - start + 1);
	}
	return longestSubstring;
}

Java

class Solution {
	int longestSubstringWithoutRepeat(String s) {
	    int n = s.length();
		int longestSubstring = 0;
		int[] previousIndex = new int[26];
		for (int i = 0; i < 26; i++) {
			previousIndex[i] = - 1;
		}
		int start = 0;
		for (int i = 0; i < n; i++) {
			if (previousIndex[s.charAt(i) - 'a'] >= start) {
				start = previousIndex[s.charAt(i) - 'a'] + 1;
			}
			previousIndex[s.charAt(i) - 'a'] = i;
			longestSubstring = Math.max(longestSubstring, i - start + 1);
		}
		return longestSubstring;
	}
}