Tasks Details
medium
Concatenate the given words in such a way as to obtain a single word with the longest possible substring composed of one particular letter.
Task Score
100%
Correctness
100%
Performance
100%
An array of N words is given. Each word consists of small letters ('a' − 'z'). Our goal is to concatenate the words in such a way as to obtain a single word with the longest possible substring composed of one particular letter. Find the length of such a substring.
Write a function:
def solution(words)
that, given an array words containing N strings, returns the length of the longest substring of a word created as described above.
Examples:
1. Given N=3 and words=["aabb", "aaaa", "bbab"], your function should return 6. One of the best concatenations is words[1] + words[0] + words[2] = "aaaaaabbbbab". The longest substring is composed of letter 'a' and its length is 6.
2. Given N=3 and words=["xxbxx", "xbx", "x"], your function should return 4. One of the best concatenations is words[0] + words[2] + words[1] = "xxbxxxxbx". The longest substring is composed of letter 'x' and its length is 4.
3. Given N=4 and words=["dd", "bb", "cc", "dd"], your function should return 4. One of the best concatenations is words[0] + words[3] + words[1] + words[2] = "ddddbbcc". The longest substring is composed of letter 'd' and its length is 4.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- all the words are non−empty and consist only of lowercase letters (a−z);
- S denotes the sum of the lengths of words; S is an integer within the range [1..100,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 1 minutes
Notes
not defined yet
Code: 13:01:19 UTC,
java,
autosave
Code: 13:01:29 UTC,
py,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
def add_complete(letter, lenght, index, complete_word):
words = complete_word.get(letter)
if not words:
words = []
complete_word[letter] = words
words.append((lenght, index))
def fast_solution(words):
prefixes = {}
complete_words = {}
letters = set()
suffixes = {}
best_concat = 0
for i in range(len(words)):
word = words[i]
initial_letter = word[0]
last_letter = word[-1]
letters.add(initial_letter)
letters.add(last_letter)
j = 0
while j < len(word) and word[j] == initial_letter:
j = j + 1
prefix_candidate = j
if prefix_candidate >= len(word):
add_complete(initial_letter, len(word), i, complete_words)
continue
best_prefix = prefixes.get(initial_letter)
if not best_prefix:
best_prefix = (0, -1, 0, -1)
if prefix_candidate >= best_prefix[0]:
prefixes[initial_letter] = (prefix_candidate, i, best_prefix[0], best_prefix[1])
else:
if prefix_candidate >= best_prefix[2]:
prefixes[initial_letter] = (best_prefix[0], best_prefix[1], prefix_candidate, i)
j = - 1
while word[j] == last_letter:
j = j - 1
suffix_candidate = - j - 1
best_suffix = suffixes.get(last_letter)
if not best_suffix:
best_suffix = (0, -1, 0, -1)
if suffix_candidate > best_suffix[0]:
suffixes[last_letter] = (suffix_candidate, i, best_suffix[0], best_suffix[1])
else:
if suffix_candidate >= best_suffix[2]:
suffixes[last_letter] = (best_suffix[0], best_suffix[1], suffix_candidate, i)
i = prefix_candidate
while i <= len(word) - suffix_candidate:
j = i + 1
count = 1
while j < len(word) and word[i] == word[j]:
count += 1
j += 1
if count > best_concat:
best_concat = count
i = j
for key in letters:
suffix = suffixes.get(key)
prefix = prefixes.get(key)
if not suffix:
suffix = (0, -1)
if not prefix:
prefix = (0, -1)
if suffix[1] == prefix[1] and suffix[0] > 0:
candidate = max(suffix[0] + prefix[2], prefix[0] + suffix[2])
else:
candidate = suffix[0] + prefix[0]
cwords = complete_words.get(key)
if not cwords:
cwords = []
for word in cwords:
candidate += word[0]
if candidate > best_concat:
best_concat = candidate
return best_concat
Code: 13:01:32 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
def add_complete(letter, lenght, index, complete_word):
words = complete_word.get(letter)
if not words:
words = []
complete_word[letter] = words
words.append((lenght, index))
def solution(words):
prefixes = {}
complete_words = {}
letters = set()
suffixes = {}
best_concat = 0
for i in range(len(words)):
word = words[i]
initial_letter = word[0]
last_letter = word[-1]
letters.add(initial_letter)
letters.add(last_letter)
j = 0
while j < len(word) and word[j] == initial_letter:
j = j + 1
prefix_candidate = j
if prefix_candidate >= len(word):
add_complete(initial_letter, len(word), i, complete_words)
continue
best_prefix = prefixes.get(initial_letter)
if not best_prefix:
best_prefix = (0, -1, 0, -1)
if prefix_candidate >= best_prefix[0]:
prefixes[initial_letter] = (prefix_candidate, i, best_prefix[0], best_prefix[1])
else:
if prefix_candidate >= best_prefix[2]:
prefixes[initial_letter] = (best_prefix[0], best_prefix[1], prefix_candidate, i)
j = - 1
while word[j] == last_letter:
j = j - 1
suffix_candidate = - j - 1
best_suffix = suffixes.get(last_letter)
if not best_suffix:
best_suffix = (0, -1, 0, -1)
if suffix_candidate > best_suffix[0]:
suffixes[last_letter] = (suffix_candidate, i, best_suffix[0], best_suffix[1])
else:
if suffix_candidate >= best_suffix[2]:
suffixes[last_letter] = (best_suffix[0], best_suffix[1], suffix_candidate, i)
i = prefix_candidate
while i <= len(word) - suffix_candidate:
j = i + 1
count = 1
while j < len(word) and word[i] == word[j]:
count += 1
j += 1
if count > best_concat:
best_concat = count
i = j
for key in letters:
suffix = suffixes.get(key)
prefix = prefixes.get(key)
if not suffix:
suffix = (0, -1)
if not prefix:
prefix = (0, -1)
if suffix[1] == prefix[1] and suffix[0] > 0:
candidate = max(suffix[0] + prefix[2], prefix[0] + suffix[2])
else:
candidate = suffix[0] + prefix[0]
cwords = complete_words.get(key)
if not cwords:
cwords = []
for word in cwords:
candidate += word[0]
if candidate > best_concat:
best_concat = candidate
return best_concat
Analysis
Code: 13:01:44 UTC,
py,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
def add_complete(letter, lenght, index, complete_word):
words = complete_word.get(letter)
if not words:
words = []
complete_word[letter] = words
words.append((lenght, index))
def solution(words):
prefixes = {}
complete_words = {}
letters = set()
suffixes = {}
best_concat = 0
for i in range(len(words)):
word = words[i]
initial_letter = word[0]
last_letter = word[-1]
letters.add(initial_letter)
letters.add(last_letter)
j = 0
while j < len(word) and word[j] == initial_letter:
j = j + 1
prefix_candidate = j
if prefix_candidate >= len(word):
add_complete(initial_letter, len(word), i, complete_words)
continue
best_prefix = prefixes.get(initial_letter)
if not best_prefix:
best_prefix = (0, -1, 0, -1)
if prefix_candidate >= best_prefix[0]:
prefixes[initial_letter] = (prefix_candidate, i, best_prefix[0], best_prefix[1])
else:
if prefix_candidate >= best_prefix[2]:
prefixes[initial_letter] = (best_prefix[0], best_prefix[1], prefix_candidate, i)
j = - 1
while word[j] == last_letter:
j = j - 1
suffix_candidate = - j - 1
best_suffix = suffixes.get(last_letter)
if not best_suffix:
best_suffix = (0, -1, 0, -1)
if suffix_candidate > best_suffix[0]:
suffixes[last_letter] = (suffix_candidate, i, best_suffix[0], best_suffix[1])
else:
if suffix_candidate >= best_suffix[2]:
suffixes[last_letter] = (best_suffix[0], best_suffix[1], suffix_candidate, i)
i = prefix_candidate
while i <= len(word) - suffix_candidate:
j = i + 1
count = 1
while j < len(word) and word[i] == word[j]:
count += 1
j += 1
if count > best_concat:
best_concat = count
i = j
for key in letters:
suffix = suffixes.get(key)
prefix = prefixes.get(key)
if not suffix:
suffix = (0, -1)
if not prefix:
prefix = (0, -1)
if suffix[1] == prefix[1] and suffix[0] > 0:
candidate = max(suffix[0] + prefix[2], prefix[0] + suffix[2])
else:
candidate = suffix[0] + prefix[0]
cwords = complete_words.get(key)
if not cwords:
cwords = []
for word in cwords:
candidate += word[0]
if candidate > best_concat:
best_concat = candidate
return best_concat
Analysis
Code: 13:01:47 UTC,
py,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
def add_complete(letter, lenght, index, complete_word):
words = complete_word.get(letter)
if not words:
words = []
complete_word[letter] = words
words.append((lenght, index))
def solution(words):
prefixes = {}
complete_words = {}
letters = set()
suffixes = {}
best_concat = 0
for i in range(len(words)):
word = words[i]
initial_letter = word[0]
last_letter = word[-1]
letters.add(initial_letter)
letters.add(last_letter)
j = 0
while j < len(word) and word[j] == initial_letter:
j = j + 1
prefix_candidate = j
if prefix_candidate >= len(word):
add_complete(initial_letter, len(word), i, complete_words)
continue
best_prefix = prefixes.get(initial_letter)
if not best_prefix:
best_prefix = (0, -1, 0, -1)
if prefix_candidate >= best_prefix[0]:
prefixes[initial_letter] = (prefix_candidate, i, best_prefix[0], best_prefix[1])
else:
if prefix_candidate >= best_prefix[2]:
prefixes[initial_letter] = (best_prefix[0], best_prefix[1], prefix_candidate, i)
j = - 1
while word[j] == last_letter:
j = j - 1
suffix_candidate = - j - 1
best_suffix = suffixes.get(last_letter)
if not best_suffix:
best_suffix = (0, -1, 0, -1)
if suffix_candidate > best_suffix[0]:
suffixes[last_letter] = (suffix_candidate, i, best_suffix[0], best_suffix[1])
else:
if suffix_candidate >= best_suffix[2]:
suffixes[last_letter] = (best_suffix[0], best_suffix[1], suffix_candidate, i)
i = prefix_candidate
while i <= len(word) - suffix_candidate:
j = i + 1
count = 1
while j < len(word) and word[i] == word[j]:
count += 1
j += 1
if count > best_concat:
best_concat = count
i = j
for key in letters:
suffix = suffixes.get(key)
prefix = prefixes.get(key)
if not suffix:
suffix = (0, -1)
if not prefix:
prefix = (0, -1)
if suffix[1] == prefix[1] and suffix[0] > 0:
candidate = max(suffix[0] + prefix[2], prefix[0] + suffix[2])
else:
candidate = suffix[0] + prefix[0]
cwords = complete_words.get(key)
if not cwords:
cwords = []
for word in cwords:
candidate += word[0]
if candidate > best_concat:
best_concat = candidate
return best_concat
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(S)
Time complexity parameters:
S - sum of the lengths of words
S - sum of the lengths of words
expand all
Correctness tests
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
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
small_words_with_long_substring
N = 4, S = 30, each word contains long substring with one letter.
N = 4, S = 30, each word contains long substring with one letter.
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
small_the_longest_prefix_and_suffix_in_one_word
N = 6, S = 50, the longest prefix and the longest suffix occur in the same word.
N = 6, S = 50, the longest prefix and the longest suffix occur in the same word.
✔
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
expand all
Correctness/performance tests
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
medium_words_with_long_substring
N = 25, S = 400, each word contains long substring with one letter.
N = 25, S = 400, each word contains long substring with one letter.
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
medium_the_longest_prefix_and_suffix_in_one_word
N = 25, S = 400, the longest prefix and the longest suffix occur in the same word.
N = 25, S = 400, the longest prefix and the longest suffix occur in the same word.
✔
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.044 s
OK
2.
0.048 s
OK
3.
0.052 s
OK
1.
0.040 s
OK
2.
0.040 s
OK
3.
0.048 s
OK
large_words_with_long_substring
S = 20,000, each word contains long substring with one letter.
S = 20,000, each word contains long substring with one letter.
✔
OK
1.
0.044 s
OK
2.
0.044 s
OK
3.
0.052 s
OK
large_the_longest_prefix_and_suffix_in_one_word
S = 20,000, the longest prefix and the longest suffix occur in the same word.
S = 20,000, the longest prefix and the longest suffix occur in the same word.
✔
OK
1.
0.044 s
OK
2.
0.044 s
OK
3.
0.048 s
OK
1.
0.044 s
OK
2.
0.044 s
OK
3.
0.048 s
OK
expand all
Performance tests
1.
0.076 s
OK
2.
0.084 s
OK
3.
0.112 s
OK
1.
0.056 s
OK
2.
0.056 s
OK
3.
0.084 s
OK
max_words_with_long_substring
S = 100,000, each word contains long substring with one letter.
S = 100,000, each word contains long substring with one letter.
✔
OK
1.
0.064 s
OK
2.
0.064 s
OK
3.
0.104 s
OK
max_the_longest_prefix_and_suffix_in_one_word
S = 100,000, the longest prefix and the longest suffix occur in the same word.
S = 100,000, the longest prefix and the longest suffix occur in the same word.
✔
OK
1.
0.068 s
OK
2.
0.068 s
OK
3.
0.100 s
OK
1.
0.080 s
OK
2.
0.072 s
OK
3.
0.100 s
OK
4.
0.352 s
OK