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].
import java.util.*;
class Solution {
public int solution(String S, int K) {
int N = S.length();
if (K == 0)
return N;
else if (K > N)
return -1;
int[][] A = new int[26][2];
int a = 0;
for (int i = 0; i < 26; i++)
A[i][0] = 2000000;
for (int i = 0; i < N; i++) {
int n = (S.charAt(i) - 'a');
if (A[n][0] == 2000000) {
A[n][0] = i;
a++;
}
A[n][1] = i;
}
if (a < K)
return -1;
if (a == K)
return 0;
Arrays.sort(A, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int R = N;
for (int i = 0; i < a; i++) {
int a1 = A[i][0], a2 = A[i][1];
for (int j = 0; j < a; j++) {
int b1 = A[j][0], b2 = A[j][1];
if (b1 < a1 || b2 < a2)
continue;
int r = 0;
for (int k = 0; k < a; k++)
if (A[k][0] < a1 || A[k][1] > b2)
r++;
if (r == K)
R = Math.min(R, b2 - a1 + 1);
}
}
return R;
}
}
import java.util.*;
class Solution {
public int solution(String S, int K) {
int N = S.length();
if (K == 0)
return N;
else if (K > N)
return -1;
int[][] A = new int[26][2];
int a = 0;
for (int i = 0; i < 26; i++)
A[i][0] = 2000000;
for (int i = 0; i < N; i++) {
int n = (S.charAt(i) - 'a');
if (A[n][0] == 2000000) {
A[n][0] = i;
a++;
}
A[n][1] = i;
}
if (a < K)
return -1;
if (a == K)
return 0;
Arrays.sort(A, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int R = N;
for (int i = 0; i < a; i++) {
int a1 = A[i][0], a2 = A[i][1];
for (int j = 0; j < a; j++) {
int b1 = A[j][0], b2 = A[j][1];
if (b1 < a1 || b2 < a2)
continue;
int r = 0;
for (int k = 0; k < a; k++)
if (A[k][0] < a1 || A[k][1] > b2)
r++;
if (r == K)
R = Math.min(R, b2 - a1 + 1);
}
}
return R;
}
}
import java.util.*;
class Solution {
public int solution(String S, int K) {
int N = S.length();
if (K == 0)
return N;
else if (K > N)
return -1;
int[][] A = new int[26][2];
int a = 0;
for (int i = 0; i < 26; i++)
A[i][0] = 2000000;
for (int i = 0; i < N; i++) {
int n = (S.charAt(i) - 'a');
if (A[n][0] == 2000000) {
A[n][0] = i;
a++;
}
A[n][1] = i;
}
if (a < K)
return -1;
if (a == K)
return 0;
Arrays.sort(A, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int R = N;
for (int i = 0; i < a; i++) {
int a1 = A[i][0], a2 = A[i][1];
for (int j = 0; j < a; j++) {
int b1 = A[j][0], b2 = A[j][1];
if (b1 < a1 || b2 < a2)
continue;
int r = 0;
for (int k = 0; k < a; k++)
if (A[k][0] < a1 || A[k][1] > b2)
r++;
if (r == K)
R = Math.min(R, b2 - a1 + 1);
}
}
return R;
}
}
The solution obtained perfect score.