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].
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;
}
}
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;
}
}
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;
}
}
The solution obtained perfect score.
S - sum of the lengths of words
N = 4, S = 30, each word contains long substring with one letter.
N = 6, S = 50, the longest prefix and the longest suffix occur in the same word.
N = 25, S = 400, each word contains long substring with one letter.
N = 25, S = 400, the longest prefix and the longest suffix occur in the same word.
S = 20,000, each word contains long substring with one letter.
S = 20,000, the longest prefix and the longest suffix occur in the same word.
S = 100,000, each word contains long substring with one letter.
S = 100,000, the longest prefix and the longest suffix occur in the same word.