# Spilt String in 3 non-empty parts such that a + b, b + c and c + a are all different strings

Issue

Given a string s, task is to count the number of ways of splitting s into three non-empty parts a, b and c in such a way that a + b, b + c and c + a are all different strings.

NOTE: + refers to string concatenation.

Example

For s “xzxzx”, the output should be countWaysToSplit(s) 5.

Consider all the ways to split s into three non-empty parts:

``````If a  "x", b  "z" and c  "xzx", then all a + b  "xz", b + c  "zxzx" and c + a  xzxx are different.
If a  "x", b  "zx" and c  "zx", then all a + b  "xzx", b + c  "zxzx" and c + a  zxx are different.
If a  "x", b  "zxz" and c  "x", then all a + b  "xzxz", b + c  "zxzx" and c + a  xx are different.
If a  "xz", b  "x" and c  "zx", then a + b  b + c  "xzx". Hence, this split is not counted.
If a  "xz", b  "xz" and c  "x", then all a + b  "xzxz", b + c  "xzx" and c + a  xxz are different.
If a  "xzx", b  "z" and c  "x", then all a + b  "xzxz", b + c  "zx" and c + a  xxzx are different.
``````

Since there are five valid ways to split s, the answer is 5.

My code for this was

``````static int countWaysToSplit(String s) {
int n  s.length();

// Loop to choose the partition
// index for the String
for (int i  1; i < n / 2; i++) {

String left  s.substring(0, i);
for (int j  i; j < n / 2; j++) {
String middle  s.substring(j, n / 2 + 1); //
String right  s.substring(middle.length() + 1, n);

if (!(middle.equals(right)) || !(middle.equals(left)) || !(right.equals(left))) {
}
}

}
}
``````

If there is a more efficient way to achieve the given solution.

Solution

I only have a very straight-forward brute force code and I do not have better solution right now. It works for the test case in the sample.

``````public int count(String str) {
//cc

int len  str.length();
int count  0;
for (int i  1; i < len - 2; i++) {
for (int j  i + 1; j < len - 1; j++) {
//              Separate the String into three parts with different index range, each lenght is at least 1
//                    String a  str.substring(0, i); // [0, i - 1]
//                    String b  str.substring(i, j); // [i, j - 1]
//                    String c  str.substring(j, len); // [j, len - 1]
String ab  str.substring(0, j); // this is [0, i - 1] + [i, j - 1]  [0, j - 1];
String bc  str.substring(i, len); // this [i, j - 1] + [j, len - 1]  [i, len - 1];
String ca  str.substring(j, len) + str.substring(0, i); // this is [j, len - 1] + [0, i - 1]
if (!(ab.equals(bc) || bc.equals(ca) || ca.equals(ab))) { // check if the three concatenation are the same, if not, add it to the count
count++;
}
}
}
return count;
}
}
``````