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();
        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