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();
int answer 0;
// 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))) {
++answer;
}
}
}
return answer;
}
```

The answer I was getting was 3 instead of 5.

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;
}
}
```

Answered By – XTX-TXT