Create substring using loop

Question

I am given a string from which i have to find out sub-strings that satisfy the following conditions

• all characters in the sub-string are same. eg: aa,bbb,cccc.

• all the character except the middle character have to be the same. eg: aba, bbabb, etc.

I've made an algo something like this

I beak the string using two loops 1st loop holds the first char and the second loop traverses through the string.

Then i send the sub-string to the vet() to see if the substring contains less than or equals two character. If the sub-string contains two character then i check if its a palindrome

public static int reverse(String s)
    {
        String wrd="";
        for(int i = s.length()-1 ;i>=0;i--)
            wrd = wrd + s.charAt(i);

        if(s.equals(wrd))
            return 1;
        else
            return 0;

    }

    public static boolean vet(String s)
    {
        HashSet<Character> hs = new HashSet<>();
        for(char c : s.toCharArray())
        {
            hs.add(c);
        }
        if(hs.size() <= 2)
            return true;
        else
            return false;
    }

    static long substrCount(int n, String s) {
        List<String> al = new ArrayList<>();

        for(int i=0;i<s.length();i++)
        {
            for(int j=i;j<s.length();j++)
            {
                        if(vet(s.substring(i,j+1)))
                        {
                            if(reverse(s.substring(i,j+1)) == 1)
                                al.add(s.substring(i,j+1));
                        }

            }
        }
        return al.size();
    }

This code works fine for small strings, however if the string is big say ten thousand character, this code will throw Time limit exception.

I suspect the loop that breaks the string and create the sub-string in the substrCount() is causing the time complexity as it has nested loops.

Please review this code and provide a better way to break the string or if the complexity is increasing due to some other section then let me know.

link : https://www.hackerrank.com/challenges/special-palindrome-again/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=strings

Answer 1

• You can collect counts from left side and right side of the string in 2 separate arrays.
• Now, we collect counts in the fashion of if previous char equals current char, increase count by 1, else set it to 1.

Example:

a  a  b  a  a  c  a  a

1  2  1  1  2  1  1  2 // left to right
2  1  1  2  1  1  2  1 // right to left

• For strings that have all characters equal, we just collect all of them while iterating itself.

• For strings with all equal except the middle character, you can use above the above table and you can collect string as below:

Pseudocode:

if(str.charAt(i-1) == str.charAt(i+1)){ // you will add checks for boundaries
    int min_count = Math.min(left[i-1],right[i+1]);
    for(int j=min_count;j>=1;--j){
        set.add(str.substring(i-j,i+j+1));
    }
}

Update:

Below is my accepted solution.

static long substrCount(int n, String s) {
    long cnt = 0;
    int[] left  = new int[n];
    int[] right = new int[n];
    int len = s.length();
    for(int i=0;i<len;++i){
        left[i] = 1;
        if(i > 0 && s.charAt(i) == s.charAt(i-1)) left[i] += left[i-1];
    }

    for(int i=len-1;i>=0;--i){
        right[i] = 1;
        if(i < len-1 && s.charAt(i) == s.charAt(i+1)) right[i] += right[i+1];
    }

    for(int i=len-1;i>=0;--i){
        if(i == 0 || i == len-1) cnt += right[i];
        else{
            if(s.charAt(i-1) == s.charAt(i+1) && s.charAt(i-1) != s.charAt(i)){
                cnt += Math.min(left[i-1],right[i+1]) + 1;
            }else if(s.charAt(i) == s.charAt(i+1)) cnt += right[i];
            else cnt++;
        }
    }

    return cnt;
}

Algorithm:

• The algorithm is the same as explained above with a few additional stuff.
• If the character is at the boundary, say 0 or at len-1, we just look at right[i] to count the strings, because we don't have a left here.

• If a character is inside this boundary, we do checks as follows:

  • If previous character equals next character, we check if previous character does not equal current character. We do this because, we want to avoid future addition of strings at the current iteration itself(say for strings like aaaaa where we are at the middle a).
  • Second condition says s.charAt(i) == s.charAt(i+1), meaning, we again have strings like aaa and we are at the first a. So we just add right[i] to indicate addition of strings like a,aa,aaa).
  • Third does cnt++ meaning addition of individual character.

• You can make a few optimizations like completely avoiding right array etc, but I leave that to you as an exercise.

• Time complexity: O(n), Space complexity: O(n)

Answer 2

Your current solution runtime is O(n^4). You can reduce it to O(n^2logn) by removing the number of character count in substrings and optimising the palindrome check portion.

To do so, you have to pre-calculate an array say "counter" where every position of the "counter" array indicates number of different characters from starting index to that position.

After constructing the array, you can check if a substring has more than two characters in O(1) by subtracting the end position and starting position value of counter array. If the value is 1 then there have only one character in the substring. If the value is 2, then you can binary search in the counter array between the substrings starting and end positions to find the position of single character. After finding out the position of the single character its straight forward to check if the substring is palindrome or not.

UPDATE! Let me explain with an example:

Suppose the string is "aaabaaa". So, the counter array would be = [1, 1, 1, 2, 2, 2, 2]; Now, lets assume for a specific time, the outer for loops value i = 1 and the inner for loops value j = 5; so the substring is "aabaa". Now to find the number of character in the substring by following code:

noOfDifferentCharacter = counter[j] - counter[i-1] + 1

If the noOfDifferentCharacter is 1 then no need to check for palindrome. If the noOfDifferentCharacter is 2 like in our case we need to check if the substring is palindrome. To check if the substring is palindrome have to perform a binary search in the counter array from index i to j to check for the position where the value is greater than its previous index. In our case the position is 3, then you just need to check if the position is the middle position of the substring. Note that the counter array is sorted.

Hope this helps. Let me know if you don't understand any step. Happy coding!