Longest Substring with K Unique Characters Editorial

Practice Problem Link: Longest Substring with K Unique Characters

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

Problem Statement

Given a string str and a number k, find the length of the longest substring in str with exactly k unique characters. If there are no possible substrings, return -1.

Naive Approach

The naive approach will be to generate all the substrings, and check which ones are valid, and take the maximum length out of all the valid substrings.

Analysis

• Time Complexity: O(n³)
• Space Complexity: O(n³)

Implementation

C++

int longestSubstringWithKUniqueCharacters(string s, int k) {
    int n = s.length();
	int answer = -1;
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j <= n; j++) {
			unordered_set<char> distinct(s.begin() + i, s.begin() + j);
			if(distinct.size() == k) {
				answer = max(answer, j - i);
			}
		}
	}
	return answer;
}

Java

class Solution {
	int longestSubstringWithKUniqueCharacters(String s, int k) {
	    int n = s.length();
		int answer = -1;
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j <= n; j++) {
				int distinct = 0;
				int count[] = new int[26];
				for(int l = i; l < j; l++) {
					count[s.charAt(l) - 'a']++;
				}
				for(int l = 0; l < 26; l++) {
					distinct += (count[l] > 0 ? 1 : 0);
				}
				if(distinct == k) {
					answer = Math.max(answer, j - i);
				}
			}
		}
		return answer;
	}
}

Optimal Approach

In the optimal approach, we can precompute sums of hashes of each alphabet in the character set from [0…..i] and use it to optimize our code. We will use 2 pointers to solve this problem in linear time. The right pointer moves forward if the answer in the current range is less than equal to K, else the left pointer moves forward. This occurs till the right pointer hits the endpoint or the left point exceeds the right pointer. For all valid ranges, we will compute the maximum length possible.

Analysis

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

Implementation

C++

int longestSubstringWithKUniqueCharacters(string s, int k) {
    int n = s.length();
	int hashChar[n][26];
	memset(hashChar, 0, sizeof(hashChar));
	unordered_set<char> distinct(s.begin(), s.end());
	for(int i = 0; i < n; i++) {
		hashChar[i][s[i] - 'a']++;
	}
	for(int i = 1; i < n; i++) {
		for(int j = 0; j < 26; j++) {
			hashChar[i][j] += hashChar[i - 1][j];
		}
	}
	auto query = [&] (int l, int r) {
		int cnt = 0;
		for(int i = 0; i < 26; i++) {
			if(l == 0) {
				cnt += hashChar[r][i] > 0;
			}
			else {
				cnt += (hashChar[r][i] - hashChar[l - 1][i]) > 0;
			}
		}
		return cnt;
	};
	if(distinct.size() < k) {
		return -1;
	}
	else {
		int left = 0, right = 0, answer = 0;
		while(right < n && left <= right) {
			if(query(left, right) <= k) {
				if(query(left, right) == k) {
					answer = max(answer, right - left + 1);
				}
				right++;
			}
			else {
				left++;
			}
		}
		return answer;
	}
}

Java

class Solution {
	int hashChar[][];
	int query(int l, int r) {
		int cnt = 0;
		for(int i = 0; i < 26; i++) {
			if(l == 0) {
				cnt += (hashChar[r][i] > 0 ? 1 : 0);
			}
			else {
				cnt += ((hashChar[r][i] - hashChar[l - 1][i]) > 0 ? 1 : 0);
			}
		}
		return cnt;
	}
	int longestSubstringWithKUniqueCharacters(String s, int k) {
	    int n = s.length();
		hashChar = new int[n][26];
		int distinct = 0;
		int count[] = new int[26];
		for(int i = 0; i < n; i++) {
			count[s.charAt(i) - 'a']++;
		}
		for(int i = 0; i < 26; i++) {
			distinct += (count[i] > 0 ? 1 : 0);
		}
		for(int i = 0; i < n; i++) {
			hashChar[i][s.charAt(i) - 'a']++;
		}
		for(int i = 1; i < n; i++) {
			for(int j = 0; j < 26; j++) {
				hashChar[i][j] += hashChar[i - 1][j];
			}
		}
		if(distinct < k) {
			return -1;
		}
		else {
			int left = 0, right = 0, answer = 0;
			while(right < n && left <= right) {
				if(query(left, right) <= k) {
					if(query(left, right) == k) {
						answer = Math.max(answer, right - left + 1);
					}
					right++;
				}
				else {
					left++;
				}
			}
			return answer;
		}
	}
}