You are given a string S consisting of N characters and an integer K. You can modify string S by removing any substring of it. A substring is defined as a contiguous segment of a string.
The goal is to find the shortest substring of S that, after removal, leaves S containing exactly K different characters.
Write a function:
class Solution { public int solution(String S, int K); }
that, given a non-empty string S consisting of N characters and an integer K, returns the length of the shortest substring that can be removed. If there is no such substring, your function should return −1.
Examples:
1. Given S = "abaacbca" and K = 2, your function should return 3. After removing substring "cbc", string S will contain exactly two different characters: a and b.
2. Given S = "aabcabc" and K = 1, your function should return 5. After removing "bcabc", string S will contain exactly one character: a.
3. Given S = "zaaaa" and K = 1, your function should return 1. You can remove only one letter: z.
4. Given S = "aaaa" and K = 2, your function should return −1. There is no such substring of S that, after removal, leaves S containing exactly 2 different characters.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..1,000,000];
- string S is made only of lowercase letters (a−z);
- K is an integer within the range [0..26].
class Solution {
public int solution(String s, int k) {
int sLength = s.length();
int allLettersCount = 'z'-'a'+1;
int diffLettersCount = 0;
int[] occurs = new int[allLettersCount];
for (int i = 0; i < sLength; i++) {
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount++;
}
occurs[s.charAt(i)-'a']++;
}
if (diffLettersCount < k || (diffLettersCount == k && diffLettersCount == sLength)) {
return -1;
}
if (diffLettersCount == k && sLength > diffLettersCount) {
return 1;
}
int i = 0;
while(diffLettersCount != k) {
occurs[s.charAt(i)-'a']--;
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount--;
}
i++;
}
int minSubstringLength = i;
int globalMinSubstringLength = minSubstringLength;
int j = i;
i = 0;
while(i < sLength - 1) {
if (occurs[s.charAt(i)-'a'] != 0) {
occurs[s.charAt(i)-'a']++;
i++;
minSubstringLength--;
if (minSubstringLength < globalMinSubstringLength) {
globalMinSubstringLength = minSubstringLength;
}
} else {
if (j == sLength) {
break;
}
occurs[s.charAt(i)-'a'] = 1;
i++;
diffLettersCount++;
minSubstringLength--;
while(diffLettersCount != k && j < sLength) {
occurs[s.charAt(j)-'a']--;
if (occurs[s.charAt(j)-'a'] == 0) {
diffLettersCount--;
}
minSubstringLength++;
j++;
}
if (diffLettersCount != k && j == sLength) {
break;
}
}
}
return globalMinSubstringLength;
}
}
class Solution {
public int solution(String s, int k) {
int sLength = s.length();
int allLettersCount = 'z'-'a'+1;
int diffLettersCount = 0;
int[] occurs = new int[allLettersCount];
for (int i = 0; i < sLength; i++) {
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount++;
}
occurs[s.charAt(i)-'a']++;
}
if (diffLettersCount < k || (diffLettersCount == k && diffLettersCount == sLength)) {
return -1;
}
if (diffLettersCount == k && sLength >= diffLettersCount) {
return 1;
}
int i = 0;
while(diffLettersCount != k) {
occurs[s.charAt(i)-'a']--;
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount--;
}
i++;
}
int minSubstringLength = i;
int globalMinSubstringLength = minSubstringLength;
int j = i;
i = 0;
while(i < sLength - 1) {
if (occurs[s.charAt(i)-'a'] != 0) {
occurs[s.charAt(i)-'a']++;
i++;
minSubstringLength--;
if (minSubstringLength < globalMinSubstringLength) {
globalMinSubstringLength = minSubstringLength;
}
} else {
if (j == sLength) {
break;
}
occurs[s.charAt(i)-'a'] = 1;
i++;
diffLettersCount++;
minSubstringLength--;
while(diffLettersCount != k && j < sLength) {
occurs[s.charAt(j)-'a']--;
if (occurs[s.charAt(j)-'a'] == 0) {
diffLettersCount--;
}
minSubstringLength++;
j++;
}
if (diffLettersCount != k && j == sLength) {
break;
}
}
}
return globalMinSubstringLength;
}
}
class Solution {
public int solution(String s, int k) {
int sLength = s.length();
int allLettersCount = 'z'-'a'+1;
int diffLettersCount = 0;
int[] occurs = new int[allLettersCount];
for (int i = 0; i < sLength; i++) {
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount++;
}
occurs[s.charAt(i)-'a']++;
}
if (diffLettersCount < k || (diffLettersCount == k && diffLettersCount == sLength)) {
return -1;
}
if (diffLettersCount == k && sLength >= diffLettersCount) {
return 0;
}
int i = 0;
while(diffLettersCount != k) {
occurs[s.charAt(i)-'a']--;
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount--;
}
i++;
}
int minSubstringLength = i;
int globalMinSubstringLength = minSubstringLength;
int j = i;
i = 0;
while(i < sLength - 1) {
if (occurs[s.charAt(i)-'a'] != 0) {
occurs[s.charAt(i)-'a']++;
i++;
minSubstringLength--;
if (minSubstringLength < globalMinSubstringLength) {
globalMinSubstringLength = minSubstringLength;
}
} else {
if (j == sLength) {
break;
}
occurs[s.charAt(i)-'a'] = 1;
i++;
diffLettersCount++;
minSubstringLength--;
while(diffLettersCount != k && j < sLength) {
occurs[s.charAt(j)-'a']--;
if (occurs[s.charAt(j)-'a'] == 0) {
diffLettersCount--;
}
minSubstringLength++;
j++;
}
if (diffLettersCount != k && j == sLength) {
break;
}
}
}
return globalMinSubstringLength;
}
}
class Solution {
public int solution(String s, int k) {
int sLength = s.length();
int allLettersCount = 'z'-'a'+1;
int diffLettersCount = 0;
int[] occurs = new int[allLettersCount];
for (int i = 0; i < sLength; i++) {
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount++;
}
occurs[s.charAt(i)-'a']++;
}
if (diffLettersCount < k || (diffLettersCount == k && diffLettersCount == sLength)) {
return -1;
}
if (diffLettersCount == k) {
return 0;
}
int i = 0;
while(diffLettersCount != k) {
occurs[s.charAt(i)-'a']--;
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount--;
}
i++;
}
int minSubstringLength = i;
int globalMinSubstringLength = minSubstringLength;
int j = i;
i = 0;
while(i < sLength - 1) {
if (occurs[s.charAt(i)-'a'] != 0) {
occurs[s.charAt(i)-'a']++;
i++;
minSubstringLength--;
if (minSubstringLength < globalMinSubstringLength) {
globalMinSubstringLength = minSubstringLength;
}
} else {
if (j == sLength) {
break;
}
occurs[s.charAt(i)-'a'] = 1;
i++;
diffLettersCount++;
minSubstringLength--;
while(diffLettersCount != k && j < sLength) {
occurs[s.charAt(j)-'a']--;
if (occurs[s.charAt(j)-'a'] == 0) {
diffLettersCount--;
}
minSubstringLength++;
j++;
}
if (diffLettersCount != k && j == sLength) {
break;
}
}
}
return globalMinSubstringLength;
}
}
class Solution {
public int solution(String s, int k) {
int sLength = s.length();
int allLettersCount = 'z'-'a'+1;
int diffLettersCount = 0;
int[] occurs = new int[allLettersCount];
for (int i = 0; i < sLength; i++) {
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount++;
}
occurs[s.charAt(i)-'a']++;
}
if (diffLettersCount < k) {
return -1;
}
if (diffLettersCount == k) {
return 0;
}
int i = 0;
while(diffLettersCount != k) {
occurs[s.charAt(i)-'a']--;
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount--;
}
i++;
}
int minSubstringLength = i;
int globalMinSubstringLength = minSubstringLength;
int j = i;
i = 0;
while(i < sLength - 1) {
if (occurs[s.charAt(i)-'a'] != 0) {
occurs[s.charAt(i)-'a']++;
i++;
minSubstringLength--;
if (minSubstringLength < globalMinSubstringLength) {
globalMinSubstringLength = minSubstringLength;
}
} else {
if (j == sLength) {
break;
}
occurs[s.charAt(i)-'a'] = 1;
i++;
diffLettersCount++;
minSubstringLength--;
while(diffLettersCount != k && j < sLength) {
occurs[s.charAt(j)-'a']--;
if (occurs[s.charAt(j)-'a'] == 0) {
diffLettersCount--;
}
minSubstringLength++;
j++;
}
if (diffLettersCount != k && j == sLength) {
break;
}
}
}
return globalMinSubstringLength;
}
}
class Solution {
public int solution(String s, int k) {
int sLength = s.length();
int allLettersCount = 'z'-'a'+1;
int diffLettersCount = 0;
int[] occurs = new int[allLettersCount];
for (int i = 0; i < sLength; i++) {
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount++;
}
occurs[s.charAt(i)-'a']++;
}
if (diffLettersCount < k) {
return -1;
}
if (diffLettersCount == k) {
return 0;
}
int i = 0;
while(diffLettersCount != k) {
occurs[s.charAt(i)-'a']--;
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount--;
}
i++;
}
int minSubstringLength = i;
int globalMinSubstringLength = minSubstringLength;
int j = i;
i = 0;
while(i < sLength - 1) {
if (occurs[s.charAt(i)-'a'] != 0) {
occurs[s.charAt(i)-'a']++;
i++;
minSubstringLength--;
if (minSubstringLength < globalMinSubstringLength) {
globalMinSubstringLength = minSubstringLength;
}
} else {
if (j == sLength) {
break;
}
occurs[s.charAt(i)-'a'] = 1;
i++;
diffLettersCount++;
minSubstringLength--;
while(diffLettersCount != k && j < sLength) {
occurs[s.charAt(j)-'a']--;
if (occurs[s.charAt(j)-'a'] == 0) {
diffLettersCount--;
}
minSubstringLength++;
j++;
}
if (diffLettersCount != k && j == sLength) {
break;
}
}
}
return globalMinSubstringLength;
}
}
['a', 0]
class Solution {
public int solution(String s, int k) {
int sLength = s.length();
int allLettersCount = 'z'-'a'+1;
int diffLettersCount = 0;
int[] occurs = new int[allLettersCount];
for (int i = 0; i < sLength; i++) {
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount++;
}
occurs[s.charAt(i)-'a']++;
}
if (diffLettersCount < k) {
return -1;
}
if (diffLettersCount == k) {
return 0;
}
int i = 0;
while(diffLettersCount != k) {
occurs[s.charAt(i)-'a']--;
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount--;
}
i++;
}
int minSubstringLength = i;
int globalMinSubstringLength = minSubstringLength;
int j = i;
i = 0;
while(i < sLength - 1) {
if (occurs[s.charAt(i)-'a'] != 0) {
occurs[s.charAt(i)-'a']++;
i++;
minSubstringLength--;
if (minSubstringLength < globalMinSubstringLength) {
globalMinSubstringLength = minSubstringLength;
}
} else {
if (j == sLength) {
break;
}
occurs[s.charAt(i)-'a'] = 1;
i++;
diffLettersCount++;
minSubstringLength--;
while(diffLettersCount != k && j < sLength) {
occurs[s.charAt(j)-'a']--;
if (occurs[s.charAt(j)-'a'] == 0) {
diffLettersCount--;
}
minSubstringLength++;
j++;
}
if (diffLettersCount != k && j == sLength) {
break;
}
}
}
return globalMinSubstringLength;
}
}
['a', 1]
class Solution {
public int solution(String s, int k) {
int sLength = s.length();
int allLettersCount = 'z'-'a'+1;
int diffLettersCount = 0;
int[] occurs = new int[allLettersCount];
for (int i = 0; i < sLength; i++) {
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount++;
}
occurs[s.charAt(i)-'a']++;
}
if (diffLettersCount < k) {
return -1;
}
if (diffLettersCount == k) {
return 0;
}
int i = 0;
while(diffLettersCount != k) {
occurs[s.charAt(i)-'a']--;
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount--;
}
i++;
}
int minSubstringLength = i;
int globalMinSubstringLength = minSubstringLength;
int j = i;
i = 0;
while(i < sLength - 1) {
if (occurs[s.charAt(i)-'a'] != 0) {
occurs[s.charAt(i)-'a']++;
i++;
minSubstringLength--;
if (minSubstringLength < globalMinSubstringLength) {
globalMinSubstringLength = minSubstringLength;
}
} else {
if (j == sLength) {
break;
}
occurs[s.charAt(i)-'a'] = 1;
i++;
diffLettersCount++;
minSubstringLength--;
while(diffLettersCount != k && j < sLength) {
occurs[s.charAt(j)-'a']--;
if (occurs[s.charAt(j)-'a'] == 0) {
diffLettersCount--;
}
minSubstringLength++;
j++;
}
if (diffLettersCount != k && j == sLength) {
break;
}
}
}
return globalMinSubstringLength;
}
}
['a', 1]
class Solution {
public int solution(String s, int k) {
int sLength = s.length();
int allLettersCount = 'z'-'a'+1;
int diffLettersCount = 0;
int[] occurs = new int[allLettersCount];
for (int i = 0; i < sLength; i++) {
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount++;
}
occurs[s.charAt(i)-'a']++;
}
if (diffLettersCount < k) {
return -1;
}
if (diffLettersCount == k) {
return 0;
}
int i = 0;
while(diffLettersCount != k) {
occurs[s.charAt(i)-'a']--;
if (occurs[s.charAt(i)-'a'] == 0) {
diffLettersCount--;
}
i++;
}
int minSubstringLength = i;
int globalMinSubstringLength = minSubstringLength;
int j = i;
i = 0;
while(i < sLength - 1) {
if (occurs[s.charAt(i)-'a'] != 0) {
occurs[s.charAt(i)-'a']++;
i++;
minSubstringLength--;
if (minSubstringLength < globalMinSubstringLength) {
globalMinSubstringLength = minSubstringLength;
}
} else {
if (j == sLength) {
break;
}
occurs[s.charAt(i)-'a'] = 1;
i++;
diffLettersCount++;
minSubstringLength--;
while(diffLettersCount != k && j < sLength) {
occurs[s.charAt(j)-'a']--;
if (occurs[s.charAt(j)-'a'] == 0) {
diffLettersCount--;
}
minSubstringLength++;
j++;
}
if (diffLettersCount != k && j == sLength) {
break;
}
}
}
return globalMinSubstringLength;
}
}
The solution obtained perfect score.