Problem statement

https://binarysearch.com/problems/Unique-String-Split/

Solution 1

Let us evaluate instead splits, for which some of two sums is equal. If for example a + b = b + c, it means than length of a and c must be the same and we have O(n) options to check, each of which has O(n) length. Similar logic for another equalities. Finally add two times case if all three parts are equal: using inclusion-exclusion formula.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, s):
        n = len(s)
        ans = (n-1)*(n-2)//2
        for i in range(1, (n+1)//2):
            if s[:n-i] == s[i:]: ans -= 1
            if s[:-i] == s[-i:] + s[:-2*i]: ans -= 1
            if s[i:] == s[2*i:] + s[:i]: ans -= 1

        if n % 3 == 0 and s[:n//3] == s[n//3:2*n//3] == s[2*n//3:]: ans += 2
        return ans

Solution 2

There is solution also using prefix functions! The idea is the following:

  1. To find number of splits, where a + b = b + c, we need to find all suffixes, which are equal to prefixes and which are longer than n//2. So, for this we look at f[n] and then recursively look back until we can.
  2. To find number of solutions a + b = c + a, we need to look at 2s, then we want to find all patterns XX.. in the beginning, where X is some string and len of XX is more than n//2.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        n = len(s)

        def kmp(s):
            n = len(s)
            f = [-1] * (n + 1)
            for i in range(1, n+1):
                f[i] = f[i-1] + 1
                while (f[i] > 0 and s[i - 1] != s[f[i] - 1]): f[i] = f[f[i] - 1] + 1
            return f

        def kmp2(t, n):
            f, ans = [-1]*(n + 1), 0
            for i in range(1, n + 1):
                f[i] = f[i-1] + 1
                while f[i] > 0 and t[i-1] != t[f[i] - 1]: f[i] = f[f[i] - 1] + 1
                if i > n//2:
                    while f[i] > i - f[i]: f[i] = f[f[i]]
                    if f[i] * 2 == i: ans += 1
                    elif i - f[i] >= n//2: break
            return ans

        ans = (n-1)*(n-2)//2
        f = kmp(s)
        x = f[n]
        while x * 2 > n:
            x = f[x]
            ans -= 1

        ans -= (kmp2(2*s, 2*n) + kmp2(2*s[::-1], 2*n))
        if n % 3 == 0 and s[:n//3] == s[n//3:2*n//3] == s[2*n//3:]: ans += 2
        return ans

Remark

There is also solution with the same complexity, using Z-function.