return count of scatter palindrome of a string [closed]

Question

We have to find scatter palindrome strings inside given string and return number of scatter palindrome in string. For example given string "aabb", the scatter palindromes are a, aa, aab, aabb, a, abb, b, bb, and b. Here there are 9 sub-strings that are scatter palindrome.

I have thought of brute force approach, i.e generating all sub-string and checking them, but I'd like to find a better approach.

Answer 1

First of all, lets consider on how you can find whether a string can be a scatter palindrome or not.

Lets consider the case where our string consists of only lowercase characters.

A string can be a considered scattered palindrome if:

1. When length of string is even: All the characters that occur in the string must occur even number of times.
2. When length of string is odd: Only one character occurs odd number of times in the string, other characters occur even number of times.

So to check whether a string can be a scatter palindrome or not, we just need to check the number of occurence of each character in the string. This can be done in O(n) where n is the length of string.

For your solution: Time complexity for generating all substrings is O(n²). And for checking whether the substring is a scatter palindrome or not we need another O(n). Hence the total time complexity is O(n³).

We can reduce the O(n) factor while checking, which can reduce the total time complexity to O(n²).

To achieve this, you can take a 2-d array of size n*26 where n is the length of the string. Let that array be A[n][26]. So A[i][j] stores the total number of occurences of j^th character* from 0 to i.

So for a string "abca", your array would look like

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Now for any substring say from index l to r, A[r]-A[l-1] gives you the occurence of each character in the substring. To check whether this can be a scatter palindrome or not we need 26 operations. Hence time complexity of the solution becomes O(n² * 26) which is asymptotically same as O(n²).

Here we are using extra space of n*26. This can be avoided by a better method.

Instead of storing the occurence of each character in an array we will store that as an integer. If i^th bit is '1' from lsb for say j^th index it means that i^th character has occured odd number of times from 0 to j^th index. If it is '0', it signifies that i^th character* has occured even number of times.

Consider this example where input string is "abca"

So our auxiliary array will be

1 3 7 6

1 -> (0001) ['a' has occured once]

3 -> (0011) ['a' and 'b' has occured once]

7 -> (0111) ['a', 'b' and 'c' has occured once each]

6 -> (0110) ['a' occured twice while 'b' and 'c' has occured once]

So now for any substring from index l to r A[r] xor A[l-1] gives the integer which will be included in the final answer if it is 0 or power of 2. (it has all 0 bits or only one '1' bit)

Pseudo-code is given below:

input string = s
ans = 0
n = s.length

for i=1:n
    A[i]=A[i-1]^(1<<(s[i-1]-97))

for i=1:n
    for j=i;n
        x=A[j]^A[i-1]
        if (x&(x-1)) == 0    //if x is a power of 2 or not 
            ans++;
        endif
    endfor
endfor

Total number of scatter palindromes is stored in ans.

The space complexity of this method is O(n). Moreover the run-time of this will be better than the method explained before.

• here i^th character refers to the character considering 'a' is 0^th character, 'b' is first character and so on.