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–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Total time used 30 minutes
Effective time used 30 minutes
Notes
not defined yet
Task timeline
Code: 07:45:39 UTC,
java,
autosave
Code: 08:13:45 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
def solution(S, K):
N = len(S)
ltor_stats = []
rtol_stats = []
letters = set()
for i, l in enumerate(S):
if l in letters:
continue
else:
ltor_stats.append(Stats(i - 1, letters))
letters = set(letters)
letters.add(l)
ltor_stats.append(Stats(i - 1, letters))
if len(ltor_stats[-1].letters) < K:
return -1
if len(ltor_stats[-1].letters) == K:
return 0
letters = set()
for i, l in enumerate(reversed(S)):
if l in letters:
continue
else:
rtol_stats.append(Stats(N - i - 1, letters))
letters = set(letters)
letters.add(l)
rtol_stats.append(Stats(N - i - 1, letters))
seen = set()
lenghts = []
def examine_substrings(lindex, rindex):
lstats = ltor_stats[lindex]
rstats = rtol_stats[rindex]
seen.add((lindex, rindex))
union = lstats.letters.union(rstats.letters)
length = rstats.index - lstats.index
if len(union) == K:
lenghts.append(length)
if lindex + 1 < len(ltor_stats) and len(ltor_stats[lindex + 1].letters) <= K:
if (lindex + 1, rindex) not in seen:
examine_substrings(lindex + 1, rindex)
if rindex + 1 < len(rtol_stats) and len(rtol_stats[rindex + 1].letters) <= K:
if (lindex, rindex + 1) not in seen:
examine_substrings(lindex, rindex + 1)
examine_substrings(0, 0)
return min(lenghts)
Code: 08:13:55 UTC,
py,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
def solution(S, K):
N = len(S)
ltor_stats = []
rtol_stats = []
letters = set()
for i, l in enumerate(S):
if l in letters:
continue
else:
ltor_stats.append(Stats(i - 1, letters))
letters = set(letters)
letters.add(l)
ltor_stats.append(Stats(i - 1, letters))
if len(ltor_stats[-1].letters) < K:
return -1
if len(ltor_stats[-1].letters) == K:
return 0
letters = set()
for i, l in enumerate(reversed(S)):
if l in letters:
continue
else:
rtol_stats.append(Stats(N - i - 1, letters))
letters = set(letters)
letters.add(l)
rtol_stats.append(Stats(N - i - 1, letters))
seen = set()
lenghts = []
def examine_substrings(lindex, rindex):
lstats = ltor_stats[lindex]
rstats = rtol_stats[rindex]
seen.add((lindex, rindex))
union = lstats.letters.union(rstats.letters)
length = rstats.index - lstats.index
if len(union) == K:
lenghts.append(length)
if lindex + 1 < len(ltor_stats) and len(ltor_stats[lindex + 1].letters) <= K:
if (lindex + 1, rindex) not in seen:
examine_substrings(lindex + 1, rindex)
if rindex + 1 < len(rtol_stats) and len(rtol_stats[rindex + 1].letters) <= K:
if (lindex, rindex + 1) not in seen:
examine_substrings(lindex, rindex + 1)
examine_substrings(0, 0)
return min(lenghts)
Code: 08:13:58 UTC,
py,
verify,
result: Failed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
def solution(S, K):
N = len(S)
ltor_stats = []
rtol_stats = []
letters = set()
for i, l in enumerate(S):
if l in letters:
continue
else:
ltor_stats.append(Stats(i - 1, letters))
letters = set(letters)
letters.add(l)
ltor_stats.append(Stats(i - 1, letters))
if len(ltor_stats[-1].letters) < K:
return -1
if len(ltor_stats[-1].letters) == K:
return 0
letters = set()
for i, l in enumerate(reversed(S)):
if l in letters:
continue
else:
rtol_stats.append(Stats(N - i - 1, letters))
letters = set(letters)
letters.add(l)
rtol_stats.append(Stats(N - i - 1, letters))
seen = set()
lenghts = []
def examine_substrings(lindex, rindex):
lstats = ltor_stats[lindex]
rstats = rtol_stats[rindex]
seen.add((lindex, rindex))
union = lstats.letters.union(rstats.letters)
length = rstats.index - lstats.index
if len(union) == K:
lenghts.append(length)
if lindex + 1 < len(ltor_stats) and len(ltor_stats[lindex + 1].letters) <= K:
if (lindex + 1, rindex) not in seen:
examine_substrings(lindex + 1, rindex)
if rindex + 1 < len(rtol_stats) and len(rtol_stats[rindex + 1].letters) <= K:
if (lindex, rindex + 1) not in seen:
examine_substrings(lindex, rindex + 1)
examine_substrings(0, 0)
return min(lenghts)
Analysis
expand all
Example tests
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 127, in <module>
main()
File "exec.py", line 89, in main
result = solution( S, K )
File "/tmp/solution.py", line 11, in solution
ltor_stats.append(Stats(i - 1, letters))
NameError: name 'Stats' is not defined
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 127, in <module>
main()
File "exec.py", line 89, in main
result = solution( S, K )
File "/tmp/solution.py", line 11, in solution
ltor_stats.append(Stats(i - 1, letters))
NameError: name 'Stats' is not defined
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 127, in <module>
main()
File "exec.py", line 89, in main
result = solution( S, K )
File "/tmp/solution.py", line 11, in solution
ltor_stats.append(Stats(i - 1, letters))
NameError: name 'Stats' is not defined
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 127, in <module>
main()
File "exec.py", line 89, in main
result = solution( S, K )
File "/tmp/solution.py", line 11, in solution
ltor_stats.append(Stats(i - 1, letters))
NameError: name 'Stats' is not defined
Code: 08:14:25 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859
from collections import namedtuple
Stats = namedtuple('Stats', ['index', 'letters'])
def solution(S, K):
N = len(S)
ltor_stats = []
rtol_stats = []
letters = set()
for i, l in enumerate(S):
if l in letters:
continue
else:
ltor_stats.append(Stats(i - 1, letters))
letters = set(letters)
letters.add(l)
ltor_stats.append(Stats(i - 1, letters))
if len(ltor_stats[-1].letters) < K:
return -1
if len(ltor_stats[-1].letters) == K:
return 0
letters = set()
for i, l in enumerate(reversed(S)):
if l in letters:
continue
else:
rtol_stats.append(Stats(N - i - 1, letters))
letters = set(letters)
letters.add(l)
rtol_stats.append(Stats(N - i - 1, letters))
seen = set()
lenghts = []
def examine_substrings(lindex, rindex):
lstats = ltor_stats[lindex]
rstats = rtol_stats[rindex]
seen.add((lindex, rindex))
union = lstats.letters.union(rstats.letters)
length = rstats.index - lstats.index
if len(union) == K:
lenghts.append(length)
if lindex + 1 < len(ltor_stats) and len(ltor_stats[lindex + 1].letters) <= K:
if (lindex + 1, rindex) not in seen:
examine_substrings(lindex + 1, rindex)
if rindex + 1 < len(rtol_stats) and len(rtol_stats[rindex + 1].letters) <= K:
if (lindex, rindex + 1) not in seen:
examine_substrings(lindex, rindex + 1)
examine_substrings(0, 0)
return min(lenghts)
Code: 08:14:33 UTC,
py,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
from collections import namedtuple
Stats = namedtuple('Stats', ['index', 'letters'])
def solution(S, K):
N = len(S)
ltor_stats = []
rtol_stats = []
letters = set()
for i, l in enumerate(S):
if l in letters:
continue
else:
ltor_stats.append(Stats(i - 1, letters))
letters = set(letters)
letters.add(l)
ltor_stats.append(Stats(i - 1, letters))
if len(ltor_stats[-1].letters) < K:
return -1
if len(ltor_stats[-1].letters) == K:
return 0
letters = set()
for i, l in enumerate(reversed(S)):
if l in letters:
continue
else:
rtol_stats.append(Stats(N - i - 1, letters))
letters = set(letters)
letters.add(l)
rtol_stats.append(Stats(N - i - 1, letters))
seen = set()
lenghts = []
def examine_substrings(lindex, rindex):
lstats = ltor_stats[lindex]
rstats = rtol_stats[rindex]
seen.add((lindex, rindex))
union = lstats.letters.union(rstats.letters)
length = rstats.index - lstats.index
if len(union) == K:
lenghts.append(length)
if lindex + 1 < len(ltor_stats) and len(ltor_stats[lindex + 1].letters) <= K:
if (lindex + 1, rindex) not in seen:
examine_substrings(lindex + 1, rindex)
if rindex + 1 < len(rtol_stats) and len(rtol_stats[rindex + 1].letters) <= K:
if (lindex, rindex + 1) not in seen:
examine_substrings(lindex, rindex + 1)
examine_substrings(0, 0)
return min(lenghts)
Analysis
Code: 08:14:49 UTC,
py,
verify,
result: Passed
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
from collections import namedtuple
Stats = namedtuple('Stats', ['index', 'letters'])
def solution(S, K):
N = len(S)
ltor_stats = []
rtol_stats = []
letters = set()
for i, l in enumerate(S):
if l in letters:
continue
else:
ltor_stats.append(Stats(i - 1, letters))
letters = set(letters)
letters.add(l)
ltor_stats.append(Stats(i - 1, letters))
if len(ltor_stats[-1].letters) < K:
return -1
if len(ltor_stats[-1].letters) == K:
return 0
letters = set()
for i, l in enumerate(reversed(S)):
if l in letters:
continue
else:
rtol_stats.append(Stats(N - i - 1, letters))
letters = set(letters)
letters.add(l)
rtol_stats.append(Stats(N - i - 1, letters))
seen = set()
lenghts = []
def examine_substrings(lindex, rindex):
lstats = ltor_stats[lindex]
rstats = rtol_stats[rindex]
seen.add((lindex, rindex))
union = lstats.letters.union(rstats.letters)
length = rstats.index - lstats.index
if len(union) == K:
lenghts.append(length)
if lindex + 1 < len(ltor_stats) and len(ltor_stats[lindex + 1].letters) <= K:
if (lindex + 1, rindex) not in seen:
examine_substrings(lindex + 1, rindex)
if rindex + 1 < len(rtol_stats) and len(rtol_stats[rindex + 1].letters) <= K:
if (lindex, rindex + 1) not in seen:
examine_substrings(lindex, rindex + 1)
examine_substrings(0, 0)
return min(lenghts)
Analysis
Code: 08:14:51 UTC,
py,
final,
score:
100
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
from collections import namedtuple
Stats = namedtuple('Stats', ['index', 'letters'])
def solution(S, K):
N = len(S)
ltor_stats = []
rtol_stats = []
letters = set()
for i, l in enumerate(S):
if l in letters:
continue
else:
ltor_stats.append(Stats(i - 1, letters))
letters = set(letters)
letters.add(l)
ltor_stats.append(Stats(i - 1, letters))
if len(ltor_stats[-1].letters) < K:
return -1
if len(ltor_stats[-1].letters) == K:
return 0
letters = set()
for i, l in enumerate(reversed(S)):
if l in letters:
continue
else:
rtol_stats.append(Stats(N - i - 1, letters))
letters = set(letters)
letters.add(l)
rtol_stats.append(Stats(N - i - 1, letters))
seen = set()
lenghts = []
def examine_substrings(lindex, rindex):
lstats = ltor_stats[lindex]
rstats = rtol_stats[rindex]
seen.add((lindex, rindex))
union = lstats.letters.union(rstats.letters)
length = rstats.index - lstats.index
if len(union) == K:
lenghts.append(length)
if lindex + 1 < len(ltor_stats) and len(ltor_stats[lindex + 1].letters) <= K:
if (lindex + 1, rindex) not in seen:
examine_substrings(lindex + 1, rindex)
if rindex + 1 < len(rtol_stats) and len(rtol_stats[rindex + 1].letters) <= K:
if (lindex, rindex + 1) not in seen:
examine_substrings(lindex, rindex + 1)
examine_substrings(0, 0)
return min(lenghts)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.036 s
OK
2.
0.040 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.040 s
OK
1.
0.040 s
OK
2.
0.048 s
OK
3.
0.044 s
OK
4.
0.052 s
OK
1.
0.160 s
OK
2.
0.176 s
OK
3.
0.172 s
OK
4.
0.172 s
OK
5.
0.176 s
OK