Tasks Details
medium
Given a string, find the shortest substring that can be removed to yield a string that contains exactly K different characters.
Task Score
100%
Correctness
100%
Performance
100%
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:
def solution(S, 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].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 1 minutes
Notes
not defined yet
Code: 14:05:20 UTC,
java,
autosave
Code: 14:05:28 UTC,
java,
autosave
#creating new element substring that including two other substrings [begining, end, lenght]
def create_element (a,b):
e1=min(a[0],b[0])
e2=max(a[1],b[1])
return ([e1,e2,e2-e1+1])
def solution(S, K):
#creating of two dimensioned array
results = []
n=len(S)
for x in range (0,26): results.append([-1]*3)
#going through string and counting first and last matches to letter and storing results to array
for x in range(0,len(S)):
m=ord(S[x])-97
if results[m][0]==-1: results[m][0]=results[m][1]=x
else: results[m][1]=x
#removing empty elements from results and counting lenght
x=0
while (x<=len(results)-1):
if results[x][0]==-1: results.pop(x)
else:
results[x]=create_element(results[x],results[x])
x += 1
#searching result. first expections that doesnt needs counting
if len(results)<K: n=-1
elif (len(results)==K): n=0
elif (K==0): n=len(S)
#and finally rest of cases
else:
rounds=len(results)-K-1 #amount of rounds minus one, because last round is searching for final result
results.sort() #sorting array to avoid mess in calculations
for x in range(0,rounds):
tmp=[]
for y in range (0,len(results)-1):
localmin=[0,n-1,n] #full string/largest possible substring
for z in range(y+1,len(results)):
element=create_element(results[y],results[z])
if element[2]<localmin[2]: localmin=element
tmp.append(localmin) #storing smallest possible sum of substrings
results = tmp #storing results for next round
#last round/finding result
for x in results: n=min(n,x[2])
return (n)
Code: 14:05:33 UTC,
py,
verify,
result: Passed
#creating new element substring that including two other substrings [begining, end, lenght]
def create_element (a,b):
e1=min(a[0],b[0])
e2=max(a[1],b[1])
return ([e1,e2,e2-e1+1])
def solution(S, K):
#creating of two dimensioned array
results = []
n=len(S)
for x in range (0,26): results.append([-1]*3)
#going through string and counting first and last matches to letter and storing results to array
for x in range(0,len(S)):
m=ord(S[x])-97
if results[m][0]==-1: results[m][0]=results[m][1]=x
else: results[m][1]=x
#removing empty elements from results and counting lenght
x=0
while (x<=len(results)-1):
if results[x][0]==-1: results.pop(x)
else:
results[x]=create_element(results[x],results[x])
x += 1
#searching result. first expections that doesnt needs counting
if len(results)<K: n=-1
elif (len(results)==K): n=0
elif (K==0): n=len(S)
#and finally rest of cases
else:
rounds=len(results)-K-1 #amount of rounds minus one, because last round is searching for final result
results.sort() #sorting array to avoid mess in calculations
for x in range(0,rounds):
tmp=[]
for y in range (0,len(results)-1):
localmin=[0,n-1,n] #full string/largest possible substring
for z in range(y+1,len(results)):
element=create_element(results[y],results[z])
if element[2]<localmin[2]: localmin=element
tmp.append(localmin) #storing smallest possible sum of substrings
results = tmp #storing results for next round
#last round/finding result
for x in results: n=min(n,x[2])
return (n)
Analysis
Code: 14:05:38 UTC,
py,
verify,
result: Passed
#creating new element substring that including two other substrings [begining, end, lenght]
def create_element (a,b):
e1=min(a[0],b[0])
e2=max(a[1],b[1])
return ([e1,e2,e2-e1+1])
def solution(S, K):
#creating of two dimensioned array
results = []
n=len(S)
for x in range (0,26): results.append([-1]*3)
#going through string and counting first and last matches to letter and storing results to array
for x in range(0,len(S)):
m=ord(S[x])-97
if results[m][0]==-1: results[m][0]=results[m][1]=x
else: results[m][1]=x
#removing empty elements from results and counting lenght
x=0
while (x<=len(results)-1):
if results[x][0]==-1: results.pop(x)
else:
results[x]=create_element(results[x],results[x])
x += 1
#searching result. first expections that doesnt needs counting
if len(results)<K: n=-1
elif (len(results)==K): n=0
elif (K==0): n=len(S)
#and finally rest of cases
else:
rounds=len(results)-K-1 #amount of rounds minus one, because last round is searching for final result
results.sort() #sorting array to avoid mess in calculations
for x in range(0,rounds):
tmp=[]
for y in range (0,len(results)-1):
localmin=[0,n-1,n] #full string/largest possible substring
for z in range(y+1,len(results)):
element=create_element(results[y],results[z])
if element[2]<localmin[2]: localmin=element
tmp.append(localmin) #storing smallest possible sum of substrings
results = tmp #storing results for next round
#last round/finding result
for x in results: n=min(n,x[2])
return (n)
Analysis
Code: 14:05:42 UTC,
py,
final,
score:
100
#creating new element substring that including two other substrings [begining, end, lenght]
def create_element (a,b):
e1=min(a[0],b[0])
e2=max(a[1],b[1])
return ([e1,e2,e2-e1+1])
def solution(S, K):
#creating of two dimensioned array
results = []
n=len(S)
for x in range (0,26): results.append([-1]*3)
#going through string and counting first and last matches to letter and storing results to array
for x in range(0,len(S)):
m=ord(S[x])-97
if results[m][0]==-1: results[m][0]=results[m][1]=x
else: results[m][1]=x
#removing empty elements from results and counting lenght
x=0
while (x<=len(results)-1):
if results[x][0]==-1: results.pop(x)
else:
results[x]=create_element(results[x],results[x])
x += 1
#searching result. first expections that doesnt needs counting
if len(results)<K: n=-1
elif (len(results)==K): n=0
elif (K==0): n=len(S)
#and finally rest of cases
else:
rounds=len(results)-K-1 #amount of rounds minus one, because last round is searching for final result
results.sort() #sorting array to avoid mess in calculations
for x in range(0,rounds):
tmp=[]
for y in range (0,len(results)-1):
localmin=[0,n-1,n] #full string/largest possible substring
for z in range(y+1,len(results)):
element=create_element(results[y],results[z])
if element[2]<localmin[2]: localmin=element
tmp.append(localmin) #storing smallest possible sum of substrings
results = tmp #storing results for next round
#last round/finding result
for x in results: n=min(n,x[2])
return (n)Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
expand all
Correctness/performance tests
1.
0.040 s
OK
2.
0.036 s
OK
3.
0.040 s
OK
4.
0.040 s
OK
5.
0.036 s
OK
1.
0.040 s
OK
2.
0.064 s
OK
3.
0.048 s
OK
4.
0.060 s
OK
1.
0.300 s
OK
2.
0.292 s
OK
3.
0.292 s
OK
4.
0.296 s
OK
5.
0.300 s
OK