Tasks Details
hard
Given a string S, find the length of the longest balanced substring of S.
Task Score
54%
Correctness
100%
Performance
0%
A string is balanced if it consists of exactly two different characters and both of those characters appear exactly the same number of times. For example: "aabbab" is balanced (both 'a' and 'b' occur three times) but "aabba" is not balanced ('a' occurs three times, 'b' occurs two times). String "aabbcc" is also not balanced (it contains three different letters).
A substring of string S is a string that consists of consecutive letters in S. For example: "ompu" is a substring of "computer" but "cmptr" is not.
Write a function solution that, given a string S, returns the length of the longest balanced substring of S.
Examples:
1. Given S = "cabbacc", the function should return 4 ("abba" is the longest balanced substring).
2. Given S = "abababa", the function should return 6 ("ababab" and "bababa" are the longest balanced substrings).
3. Given S = "aaaaaaa", the function should return 0 (S does not contain a balanced substring).
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- string S is made only of lowercase letters (a−z).
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 2 minutes
Notes
not defined yet
Code: 07:12:41 UTC,
java,
autosave
Code: 07:13:00 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String S) {
int max=0;
for(int i=0;i<S.length();i++){
for(int j=S.length();j>0 && j>i;j--){
String sub=S.substring(i, j);
if(sub.length()%2==0 && sub.length()>max){
boolean b= testBalance(sub);
if(b){
System.out.println(i+" "+j+" char count "+sub.chars().count() +" "+sub);
if(sub.length()>max){
max=sub.length();
}
}
}
}
}
System.out.println(max);
return max;
}
}
Code: 07:13:13 UTC,
java,
autosave
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String S) {
int max=0;
for(int i=0;i<S.length();i++){
for(int j=S.length();j>0 && j>i;j--){
String sub=S.substring(i, j);
if(sub.length()%2==0 && sub.length()>max){
boolean b= testBalance(sub);
if(b){
System.out.println(i+" "+j+" char count "+sub.chars().count() +" "+sub);
if(sub.length()>max){
max=sub.length();
}
}
}
}
}
System.out.println(max);
return max;
}
private boolean testBalance(String sub) {
Map<Character,Integer> ch= new HashMap<>();
for(int i=0;i<sub.length();i++){
if(ch.containsKey(sub.charAt(i))){
Integer k=ch.get(sub.charAt(i));
k++;
ch.put(sub.charAt(i), k);
}else{
ch.put(sub.charAt(i), 1);
}
}
boolean flag=false;
if(ch.size()==2){
Set<Integer> values = new HashSet<Integer>(ch.values());
flag = values.size() == 1;
}
return flag;
}
}
Code: 07:13:16 UTC,
java,
verify,
result: Failed
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String S) {
int max=0;
for(int i=0;i<S.length();i++){
for(int j=S.length();j>0 && j>i;j--){
String sub=S.substring(i, j);
if(sub.length()%2==0 && sub.length()>max){
boolean b= testBalance(sub);
if(b){
System.out.println(i+" "+j+" char count "+sub.chars().count() +" "+sub);
if(sub.length()>max){
max=sub.length();
}
}
}
}
}
System.out.println(max);
return max;
}
private boolean testBalance(String sub) {
Map<Character,Integer> ch= new HashMap<>();
for(int i=0;i<sub.length();i++){
if(ch.containsKey(sub.charAt(i))){
Integer k=ch.get(sub.charAt(i));
k++;
ch.put(sub.charAt(i), k);
}else{
ch.put(sub.charAt(i), 1);
}
}
boolean flag=false;
if(ch.size()==2){
Set<Integer> values = new HashSet<Integer>(ch.values());
flag = values.size() == 1;
}
return flag;
}
}
Analysis
Compile error
Solution.java:32: error: cannot find symbol Map<Character,Integer> ch= new HashMap<>(); ^ symbol: class Map location: class Solution Solution.java:32: error: cannot find symbol Map<Character,Integer> ch= new HashMap<>(); ^ symbol: class HashMap location: class Solution Solution.java:44: error: cannot find symbol Set<Integer> values = new HashSet<Integer>(ch.values()); ^ symbol: class Set location: class Solution Solution.java:44: error: cannot find symbol Set<Integer> values = new HashSet<Integer>(ch.values()); ^ symbol: class HashSet location: class Solution 4 errors
Code: 07:13:24 UTC,
java,
autosave
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String S) {
int max=0;
for(int i=0;i<S.length();i++){
for(int j=S.length();j>0 && j>i;j--){
String sub=S.substring(i, j);
if(sub.length()%2==0 && sub.length()>max){
boolean b= testBalance(sub);
if(b){
System.out.println(i+" "+j+" char count "+sub.chars().count() +" "+sub);
if(sub.length()>max){
max=sub.length();
}
}
}
}
}
System.out.println(max);
return max;
}
private boolean testBalance(String sub) {
Map<Character,Integer> ch= new HashMap<>();
for(int i=0;i<sub.length();i++){
if(ch.containsKey(sub.charAt(i))){
Integer k=ch.get(sub.charAt(i));
k++;
ch.put(sub.charAt(i), k);
}else{
ch.put(sub.charAt(i), 1);
}
}
boolean flag=false;
if(ch.size()==2){
Set<Integer> values = new HashSet<Integer>(ch.values());
flag = values.size() == 1;
}
return flag;
}
}
Code: 07:13:26 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String S) {
int max=0;
for(int i=0;i<S.length();i++){
for(int j=S.length();j>0 && j>i;j--){
String sub=S.substring(i, j);
if(sub.length()%2==0 && sub.length()>max){
boolean b= testBalance(sub);
if(b){
System.out.println(i+" "+j+" char count "+sub.chars().count() +" "+sub);
if(sub.length()>max){
max=sub.length();
}
}
}
}
}
System.out.println(max);
return max;
}
private boolean testBalance(String sub) {
Map<Character,Integer> ch= new HashMap<>();
for(int i=0;i<sub.length();i++){
if(ch.containsKey(sub.charAt(i))){
Integer k=ch.get(sub.charAt(i));
k++;
ch.put(sub.charAt(i), k);
}else{
ch.put(sub.charAt(i), 1);
}
}
boolean flag=false;
if(ch.size()==2){
Set<Integer> values = new HashSet<Integer>(ch.values());
flag = values.size() == 1;
}
return flag;
}
}
Analysis
expand all
Example tests
1.
0.096 s
OK
stdout:
0 2 char count 2 ca 1 5 char count 4 abba 4
1.
0.092 s
OK
stdout:
0 6 char count 6 ababab 6
1.
0.008 s
OK
stdout:
0
Code: 07:13:48 UTC,
java,
autosave
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String S) {
int max=0;
for(int i=0;i<S.length();i++){
for(int j=S.length();j>0 && j>i;j--){
String sub=S.substring(i, j);
if(sub.length()%2==0 && sub.length()>max){
boolean b= testBalance(sub);
if(b){
//System.out.println(i+" "+j+" char count "+sub.chars().count() +" "+sub);
if(sub.length()>max){
max=sub.length();
}
}
}
}
}
System.out.println(max);
return max;
}
private boolean testBalance(String sub) {
Map<Character,Integer> ch= new HashMap<>();
for(int i=0;i<sub.length();i++){
if(ch.containsKey(sub.charAt(i))){
Integer k=ch.get(sub.charAt(i));
k++;
ch.put(sub.charAt(i), k);
}else{
ch.put(sub.charAt(i), 1);
}
}
boolean flag=false;
if(ch.size()==2){
Set<Integer> values = new HashSet<Integer>(ch.values());
flag = values.size() == 1;
}
return flag;
}
}
Code: 07:13:58 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String S) {
int max=0;
for(int i=0;i<S.length();i++){
for(int j=S.length();j>0 && j>i;j--){
String sub=S.substring(i, j);
if(sub.length()%2==0 && sub.length()>max){
boolean b= testBalance(sub);
if(b){
//System.out.println(i+" "+j+" char count "+sub.chars().count() +" "+sub);
if(sub.length()>max){
max=sub.length();
}
}
}
}
}
// System.out.println(max);
return max;
}
private boolean testBalance(String sub) {
Map<Character,Integer> ch= new HashMap<>();
for(int i=0;i<sub.length();i++){
if(ch.containsKey(sub.charAt(i))){
Integer k=ch.get(sub.charAt(i));
k++;
ch.put(sub.charAt(i), k);
}else{
ch.put(sub.charAt(i), 1);
}
}
boolean flag=false;
if(ch.size()==2){
Set<Integer> values = new HashSet<Integer>(ch.values());
flag = values.size() == 1;
}
return flag;
}
}
Analysis
Code: 07:14:27 UTC,
java,
verify,
result: Passed
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String S) {
int max=0;
for(int i=0;i<S.length();i++){
for(int j=S.length();j>0 && j>i;j--){
String sub=S.substring(i, j);
if(sub.length()%2==0 && sub.length()>max){
boolean b= testBalance(sub);
if(b){
//System.out.println(i+" "+j+" char count "+sub.chars().count() +" "+sub);
if(sub.length()>max){
max=sub.length();
}
}
}
}
}
// System.out.println(max);
return max;
}
private boolean testBalance(String sub) {
Map<Character,Integer> ch= new HashMap<>();
for(int i=0;i<sub.length();i++){
if(ch.containsKey(sub.charAt(i))){
Integer k=ch.get(sub.charAt(i));
k++;
ch.put(sub.charAt(i), k);
}else{
ch.put(sub.charAt(i), 1);
}
}
boolean flag=false;
if(ch.size()==2){
Set<Integer> values = new HashSet<Integer>(ch.values());
flag = values.size() == 1;
}
return flag;
}
}
Analysis
Code: 07:14:33 UTC,
java,
final,
score:
54
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String S) {
int max=0;
for(int i=0;i<S.length();i++){
for(int j=S.length();j>0 && j>i;j--){
String sub=S.substring(i, j);
if(sub.length()%2==0 && sub.length()>max){
boolean b= testBalance(sub);
if(b){
//System.out.println(i+" "+j+" char count "+sub.chars().count() +" "+sub);
if(sub.length()>max){
max=sub.length();
}
}
}
}
}
// System.out.println(max);
return max;
}
private boolean testBalance(String sub) {
Map<Character,Integer> ch= new HashMap<>();
for(int i=0;i<sub.length();i++){
if(ch.containsKey(sub.charAt(i))){
Integer k=ch.get(sub.charAt(i));
k++;
ch.put(sub.charAt(i), k);
}else{
ch.put(sub.charAt(i), 1);
}
}
boolean flag=false;
if(ch.size()==2){
Set<Integer> values = new HashSet<Integer>(ch.values());
flag = values.size() == 1;
}
return flag;
}
}Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N**2)
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
7.
0.008 s
OK
1.
0.224 s
OK
2.
0.080 s
OK
3.
0.012 s
OK
4.
0.192 s
OK
1.
0.208 s
OK
2.
0.220 s
OK
3.
0.052 s
OK
4.
0.208 s
OK
1.
0.012 s
OK
2.
0.012 s
OK
3.
0.024 s
OK
4.
0.152 s
OK
5.
0.176 s
OK
1.
0.056 s
OK
2.
0.132 s
OK
3.
0.196 s
OK
4.
0.188 s
OK
1.
0.168 s
OK
2.
0.192 s
OK
3.
0.208 s
OK
4.
0.208 s
OK
expand all
Performance tests
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.18 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.18 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.27 sec.
4.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.30 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.18 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.18 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.18 sec.
4.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.32 sec.
5.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.35 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.18 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.24 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.37 sec.
4.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.38 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.18 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.19 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.34 sec.
4.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.37 sec.
1.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.59 sec.
2.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.64 sec.
3.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.70 sec.
4.
6.000 s
TIMEOUT ERROR,
running time: >6.00 sec., time limit: 0.62 sec.