Tasks Details
hard
1.
PartialSort
Given a string and an integer K, return the lexicographically minimum string that can be achieved by applying at most K swaps of adjacent letters.
Task Score
61%
Correctness
100%
Performance
0%
A string S is given. In one move, any two adjacent letters can be swapped. For example, given a string "abcd", it's possible to create "bacd", "acbd" or "abdc" in one such move. What is the lexicographically minimum string that can be achieved by at most K moves?
Write a function:
def solution(S, K)
that, given a string S of length N and an integer K, returns the lexicographically minimum string that can be achieved by at most K swaps of any adjacent letters.
Examples:
1. Given S = "decade" and K = 4, your function should return "adcede". Swaps could be:
decade → dceade,
dceade → dcaede,
dcaede → dacede,
dacede → adcede.
2. Given S = "bbbabbb" and K = 2, your function should return "babbbbb". The swaps are:
bbbabbb → bbabbbb,
bbabbbb → babbbbb.
3. Given S = "abracadabra" and K = 15, your function should return "aaaaabrcdbr".
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- string S consists only of lowercase letters ('a'-'z');
- K is an integer within the range [0..1,000,000,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 22 minutes
Notes
not defined yet
Code: 11:26:58 UTC,
java,
autosave
Code: 11:36:10 UTC,
py,
autosave
Code: 11:36:20 UTC,
py,
autosave
Code: 11:39:59 UTC,
py,
autosave
Code: 11:40:09 UTC,
py,
autosave
Code: 11:40:39 UTC,
py,
autosave
Code: 11:40:49 UTC,
py,
autosave
Code: 11:41:25 UTC,
py,
autosave
Code: 11:41:41 UTC,
py,
autosave
Code: 11:43:29 UTC,
py,
autosave
Code: 11:43:44 UTC,
py,
autosave
Code: 11:43:55 UTC,
py,
autosave
Code: 11:44:26 UTC,
py,
autosave
Code: 11:44:44 UTC,
py,
autosave
Code: 11:45:08 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(S, K):
for i in range(len(S)):
pos = i
for j in range(i, len(S)):
if (j - i) > K:
break
if S[j] < S[pos]:
pos = j
for j in range(pos, i, -1):
S[j], S[j-1] = S[j-1], S[j]
Code: 11:45:20 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(S, K):
for i in range(len(S)):
pos = i
for j in range(i, len(S)):
if (j - i) > K:
break
if S[j] < S[pos]:
pos = j
for j in range(pos, i, -1):
S[j], S[j-1] = S[j-1], S[j]
K -= pos - i
Code: 11:45:45 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(S, K):
for i in range(len(S)):
pos = i
for j in range(i, len(S)):
if (j - i) > K:
break
if S[j] < S[pos]:
pos = j
for j in range(pos, i, -1):
S[j], S[j-1] = S[j-1], S[j]
K -= pos - i
Code: 11:46:09 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(S, K):
S = list(S)
for i in range(len(S)):
pos = i
for j in range(i, len(S)):
if (j - i) > K:
break
if S[j] < S[pos]:
pos = j
for j in range(pos, i, -1):
S[j], S[j-1] = S[j-1], S[j]
K -= pos - i
Code: 11:47:15 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(S, K):
S = list(S)
for i in range(len(S)):
pos = i
for j in range(i, len(S)):
if (j - i) > K:
break
if S[j] < S[pos]:
pos = j
for j in range(pos, i, -1):
S[j], S[j-1] = S[j-1], S[j]
K -= pos - i
retu
Code: 11:47:29 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(S, K):
S = list(S)
for i in range(len(S)):
pos = i
for j in range(i, len(S)):
if (j - i) > K:
break
if S[j] < S[pos]:
pos = j
for j in range(pos, i, -1):
S[j], S[j-1] = S[j-1], S[j]
K -= pos - i
return ''.join
Code: 11:47:40 UTC,
py,
autosave
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(S, K):
S = list(S)
for i in range(len(S)):
pos = i
for j in range(i, len(S)):
if (j - i) > K:
break
if S[j] < S[pos]:
pos = j
for j in range(pos, i, -1):
S[j], S[j-1] = S[j-1], S[j]
K -= pos - i
return ''.join(S)
Code: 11:47:45 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(S, K):
S = list(S)
for i in range(len(S)):
pos = i
for j in range(i, len(S)):
if (j - i) > K:
break
if S[j] < S[pos]:
pos = j
for j in range(pos, i, -1):
S[j], S[j-1] = S[j-1], S[j]
K -= pos - i
return ''.join(S)
Analysis
Code: 11:47:57 UTC,
py,
verify,
result: Passed
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(S, K):
S = list(S)
for i in range(len(S)):
pos = i
for j in range(i, len(S)):
if (j - i) > K:
break
if S[j] < S[pos]:
pos = j
for j in range(pos, i, -1):
S[j], S[j-1] = S[j-1], S[j]
K -= pos - i
return ''.join(S)
Analysis
Code: 11:48:00 UTC,
py,
final,
score:
61
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(S, K):
S = list(S)
for i in range(len(S)):
pos = i
for j in range(i, len(S)):
if (j - i) > K:
break
if S[j] < S[pos]:
pos = j
for j in range(pos, i, -1):
S[j], S[j-1] = S[j-1], S[j]
K -= pos - i
return ''.join(S)
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N**2) or O(N * min(K, N))
expand all
Correctness tests
1.
0.036 s
OK
2.
0.040 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
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
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
7.
0.036 s
OK
8.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
5.
0.036 s
OK
6.
0.036 s
OK
7.
0.036 s
OK
8.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
expand all
Performance tests
1.
10.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 10.000 sec.
2.
10.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 10.000 sec.
3.
10.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 10.000 sec.
4.
10.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 10.000 sec.
almost_sorted_big
String sorted almost to the end, N = 80,000, K = 50,000.
String sorted almost to the end, N = 80,000, K = 50,000.
✘
TIMEOUT ERROR
Killed. Hard limit reached: 13.000 sec.
Killed. Hard limit reached: 13.000 sec.
1.
13.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 13.000 sec.
2.
13.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 13.000 sec.
3.
13.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 13.000 sec.
4.
13.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 13.000 sec.
descending_big
Most of the string consists of letters sorted in descending order, N = 80,000.
Most of the string consists of letters sorted in descending order, N = 80,000.
✘
TIMEOUT ERROR
Killed. Hard limit reached: 14.000 sec.
Killed. Hard limit reached: 14.000 sec.
1.
14.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 14.000 sec.
2.
13.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 13.000 sec.
3.
13.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 13.000 sec.
4.
13.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 13.000 sec.
5.
0.492 s
OK
6.
0.488 s
OK
7.
0.484 s
OK
8.
0.480 s
OK
almost_mono_big
Single repeating letter plus a short suffix.
Single repeating letter plus a short suffix.
✘
TIMEOUT ERROR
Killed. Hard limit reached: 14.000 sec.
Killed. Hard limit reached: 14.000 sec.
1.
14.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 14.000 sec.
2.
15.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 15.000 sec.
3.
15.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 15.000 sec.
1.
15.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 15.000 sec.
2.
15.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 15.000 sec.
3.
15.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 15.000 sec.
4.
15.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 15.000 sec.