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:
class Solution { public int solution(String[] 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 Java 21
Time spent on task 1 minutes
Notes
not defined yet
Code: 11:10:58 UTC,
java,
autosave
Code: 11:11:03 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125
import java.util.*;
class Solution {
class Node {
int left, right, middle;
int bigLeft, bigRight;
int within;
void add(int m) {
middle += m;
}
void setWithin(int w) {
within = Math.max(w, within);
}
void add(int l, int r) {
if (l == 0 && r > right)
right = r;
else if (r == 0 && l > left)
left = l;
else if (l < left && r > right)
right = r;
else if (r < right && l > left)
left = l;
else if (l >= left && r >= right) {
addBig(l, r);
return;
}
updateBig();
}
void updateBig() {
if (bigLeft == 0)
return;
if (left >= bigLeft) {
if (bigRight > right)
right = bigRight;
bigLeft = 0;
} else if (right >= bigRight) {
if (bigLeft > left)
left = bigLeft;
bigLeft = 0;
}
}
void addBig(int l, int r) {
if (bigLeft == 0) {
bigLeft = l;
bigRight = r;
} else {
if (l >= bigLeft && r >= bigRight) {
left = bigLeft;
right = bigRight;
bigLeft = l;
bigRight = r;
} else if (l < bigLeft && r < bigRight) {
left = l;
right = r;
} else {
left = Math.max(l, bigLeft);
right = Math.max(r, bigRight);
bigLeft = 0;
}
}
}
}
public int solution(String[] words) {
int N = words.length;
Node[] n = new Node[26];
for (int i = 0; i < 26; i++)
n[i] = new Node();
for (int i = 0; i < N; i++) {
char[] s = words[i].toCharArray();
int l = 0, r = 0, c = 0;
char b = 'a' - 1;
char a = b;
for (int j = 0; j < s.length; j++) {
if (j == 0) {
b = s[0];
a = b;
c = 1;
continue;
}
if (b == s[j])
c++;
else {
if (j == c)
l = j;
else
n[b - 'a'].setWithin(c);
b = s[j];
c = 1;
}
}
if (c == s.length)
n[b - 'a'].add(c);
else {
r = c;
if (a == b)
n[b - 'a'].add(l, r);
else {
n[a - 'a'].add(l, 0);
n[b - 'a'].add(0, r);
}
}
}
int R = 0;
for (int i = 0; i < 26; i++) {
Node m = n[i];
R = Math.max(R, m.within);
if (m.bigLeft > 0)
R = Math.max(R, m.middle + Math.max(m.bigLeft + m.right, m.bigRight + m.left));
else
R = Math.max(R, m.left + m.middle + m.right);
}
return R;
}
}
Analysis
Code: 11:11:10 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125
import java.util.*;
class Solution {
class Node {
int left, right, middle;
int bigLeft, bigRight;
int within;
void add(int m) {
middle += m;
}
void setWithin(int w) {
within = Math.max(w, within);
}
void add(int l, int r) {
if (l == 0 && r > right)
right = r;
else if (r == 0 && l > left)
left = l;
else if (l < left && r > right)
right = r;
else if (r < right && l > left)
left = l;
else if (l >= left && r >= right) {
addBig(l, r);
return;
}
updateBig();
}
void updateBig() {
if (bigLeft == 0)
return;
if (left >= bigLeft) {
if (bigRight > right)
right = bigRight;
bigLeft = 0;
} else if (right >= bigRight) {
if (bigLeft > left)
left = bigLeft;
bigLeft = 0;
}
}
void addBig(int l, int r) {
if (bigLeft == 0) {
bigLeft = l;
bigRight = r;
} else {
if (l >= bigLeft && r >= bigRight) {
left = bigLeft;
right = bigRight;
bigLeft = l;
bigRight = r;
} else if (l < bigLeft && r < bigRight) {
left = l;
right = r;
} else {
left = Math.max(l, bigLeft);
right = Math.max(r, bigRight);
bigLeft = 0;
}
}
}
}
public int solution(String[] words) {
int N = words.length;
Node[] n = new Node[26];
for (int i = 0; i < 26; i++)
n[i] = new Node();
for (int i = 0; i < N; i++) {
char[] s = words[i].toCharArray();
int l = 0, r = 0, c = 0;
char b = 'a' - 1;
char a = b;
for (int j = 0; j < s.length; j++) {
if (j == 0) {
b = s[0];
a = b;
c = 1;
continue;
}
if (b == s[j])
c++;
else {
if (j == c)
l = j;
else
n[b - 'a'].setWithin(c);
b = s[j];
c = 1;
}
}
if (c == s.length)
n[b - 'a'].add(c);
else {
r = c;
if (a == b)
n[b - 'a'].add(l, r);
else {
n[a - 'a'].add(l, 0);
n[b - 'a'].add(0, r);
}
}
}
int R = 0;
for (int i = 0; i < 26; i++) {
Node m = n[i];
R = Math.max(R, m.within);
if (m.bigLeft > 0)
R = Math.max(R, m.middle + Math.max(m.bigLeft + m.right, m.bigRight + m.left));
else
R = Math.max(R, m.left + m.middle + m.right);
}
return R;
}
}
Analysis
Code: 11:11:16 UTC,
java,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125
import java.util.*;
class Solution {
class Node {
int left, right, middle;
int bigLeft, bigRight;
int within;
void add(int m) {
middle += m;
}
void setWithin(int w) {
within = Math.max(w, within);
}
void add(int l, int r) {
if (l == 0 && r > right)
right = r;
else if (r == 0 && l > left)
left = l;
else if (l < left && r > right)
right = r;
else if (r < right && l > left)
left = l;
else if (l >= left && r >= right) {
addBig(l, r);
return;
}
updateBig();
}
void updateBig() {
if (bigLeft == 0)
return;
if (left >= bigLeft) {
if (bigRight > right)
right = bigRight;
bigLeft = 0;
} else if (right >= bigRight) {
if (bigLeft > left)
left = bigLeft;
bigLeft = 0;
}
}
void addBig(int l, int r) {
if (bigLeft == 0) {
bigLeft = l;
bigRight = r;
} else {
if (l >= bigLeft && r >= bigRight) {
left = bigLeft;
right = bigRight;
bigLeft = l;
bigRight = r;
} else if (l < bigLeft && r < bigRight) {
left = l;
right = r;
} else {
left = Math.max(l, bigLeft);
right = Math.max(r, bigRight);
bigLeft = 0;
}
}
}
}
public int solution(String[] words) {
int N = words.length;
Node[] n = new Node[26];
for (int i = 0; i < 26; i++)
n[i] = new Node();
for (int i = 0; i < N; i++) {
char[] s = words[i].toCharArray();
int l = 0, r = 0, c = 0;
char b = 'a' - 1;
char a = b;
for (int j = 0; j < s.length; j++) {
if (j == 0) {
b = s[0];
a = b;
c = 1;
continue;
}
if (b == s[j])
c++;
else {
if (j == c)
l = j;
else
n[b - 'a'].setWithin(c);
b = s[j];
c = 1;
}
}
if (c == s.length)
n[b - 'a'].add(c);
else {
r = c;
if (a == b)
n[b - 'a'].add(l, r);
else {
n[a - 'a'].add(l, 0);
n[b - 'a'].add(0, r);
}
}
}
int R = 0;
for (int i = 0; i < 26; i++) {
Node m = n[i];
R = Math.max(R, m.within);
if (m.bigLeft > 0)
R = Math.max(R, m.middle + Math.max(m.bigLeft + m.right, m.bigRight + m.left));
else
R = Math.max(R, m.left + m.middle + m.right);
}
return R;
}
}
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.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.008 s
OK
6.
0.008 s
OK
1.
0.012 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 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.008 s
OK
2.
0.004 s
OK
3.
0.008 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.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
expand all
Correctness/performance tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.012 s
OK
1.
0.008 s
OK
2.
0.012 s
OK
3.
0.012 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.008 s
OK
2.
0.008 s
OK
3.
0.012 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.012 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.012 s
OK
1.
0.024 s
OK
2.
0.028 s
OK
3.
0.032 s
OK
1.
0.020 s
OK
2.
0.020 s
OK
3.
0.032 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.020 s
OK
2.
0.016 s
OK
3.
0.032 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.020 s
OK
2.
0.024 s
OK
3.
0.032 s
OK
1.
0.020 s
OK
2.
0.024 s
OK
3.
0.032 s
OK
expand all
Performance tests
1.
0.068 s
OK
2.
0.072 s
OK
3.
0.132 s
OK
1.
0.060 s
OK
2.
0.064 s
OK
3.
0.116 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.060 s
OK
2.
0.064 s
OK
3.
0.120 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.064 s
OK
2.
0.068 s
OK
3.
0.120 s
OK
1.
0.076 s
OK
2.
0.068 s
OK
3.
0.120 s
OK
4.
0.540 s
OK