Special string again (string manipulation) + time and space complexity analysis

Summary

The problem is the following:

Given a string s of length n, determine the number of special substrings within s.

Example: For the string "abcbaba"

• The special substrings are: "a", "b", "c", "b", "a", "b", "a", "bcb", "bab", "aba"
• The total count of special substrings is 10

A special string is a:

• String in which all characters are the same: e.g. "aaaa" , or "bbbb"
• String in which all characters except the middle one are the same: "aabaa", "bbbabb"

Here is the link to the problem:

https://www.hackerrank.com/challenges/special-palindrome-again/problem

Solution

    // Complete the substrCount function below.
      private static long substrCount (int n, String s) {

        long count = 0;

        //step 1: count substrings with all identical characters
        int i = 0;
        while(i < n) {
            int charCount = 1; // keeps track of consecutive identical characters   
           while( i+1 < n && s.charAt(i) == s.charAt(i+1)) {
                i++;
                charCount++;
            }

            //Add the number of strings that can be formed from this block

            /*
            * If you have charCount consecutive identical characters,
            * the number of substrings that can be formed from this block is
            * given by the sum of the first charCount natural numbers.
            */

            count += (charCount * (charCount + 1)) / 2 ;
            i++;
        }

        //Step 2: Count substrings with one different middle character

        /*This loop iterates over each character in the string, 
         *  considering each one as a potential  middle character  
         */
        for(i = 1; i < n ; i++) {

            int charCount = 1;
            /* charCount: Represents the number of characters 
               * on each side of the middle character that are the same */
             

            while ( i - charCount >= 0  // The left side of the substring is within bounds.
                    && i + charCount < n  // The right side of the substring is within bounds.
                    && s.charAt(i - 1) != s.charAt(i) 
                    /*
                    *		Checks that the middle character (at index i) is different from 
                    *		the character immediately to the left of the middle (at index i - 1).
		    */
                    && s.charAt(i - charCount) == s.charAt(i - 1 )
                    /*         Checks that the character to the left of the middle character 
                     *           (at index i - charCount)
		     *		matches the character immediately to the left of the middle 
                     *         (at index i - 1).
                    */
                    && s.charAt(i + charCount) == s.charAt(i -1 ) 
                     /*
		       *	   Checks that the character to the right of the middle character 
                       *               (at index i + charCount)
			* 	   also matches the character immediately to the left of the middle.
			* /
                ) {
                count++;
                charCount++;
            }
        }

        return count;

    }        

Step-by-step explanation

• We initialize the count var to 0 to keep track of the special substrings
• Count substrings with all identical characters

int i = 0;
while (i < n) {
    int charCount = 1;
    while (i + 1 < n && s.charAt(i) == s.charAt(i + 1)) {
        i++;
        charCount++;
    }
    count += (charCount * (charCount + 1)) / 2;
    i++;
}        

- Outer loop: Iterate over the string s using index i

- Inner loop: Count consecutive identical characters starting from s[i]

- "charCount" keeps track of the number of consecutive identical characters.

- Calculate substrings for 'charCount' consecutive identical characters, the number of substrings

 The number of substrings is given by the formula:  (charCount?(charCount+1))/2
 This formula calculates the sum of the first charCount natural numbers, 
 representing the total number of substrings that can be formed from these characters.        

• Count substrings with one different middle character

    for(i = 1; i < n ; i++) {

            int charCount = 1;
            /* charCount: Represents the number of characters 
               * on each side of the middle character that are the same */
             

            while ( i - charCount >= 0  // The left side of the substring is within bounds.
                    && i + charCount < n  // The right side of the substring is within bounds.
                    && s.charAt(i - 1) != s.charAt(i) 
                    /*
                    *		Checks that the middle character (at index i) is different from 
                    *		the character immediately to the left of the middle (at index i - 1).
		    */
                    && s.charAt(i - charCount) == s.charAt(i - 1 )
                    /*         Checks that the character to the left of the middle character 
                     *           (at index i - charCount)
		     *		matches the character immediately to the left of the middle 
                     *         (at index i - 1).
                    */
                    && s.charAt(i + charCount) == s.charAt(i -1 ) 
                     /*
		       *	   Checks that the character to the right of the middle character 
                       *               (at index i + charCount)
			* 	   also matches the character immediately to the left of the middle.
			* /
                ) {
                count++;
                charCount++;
            }
        }
        

• Outer loop: iterate over the string 's' starting from index '1'

- We start from '1' because the middle character must have characters on both sides

• Inner loop: Check for special substrings with one different middle character

- Bounds check: Ensure the substring is within the string's boundaries

- Middle Character check: Ensure the character at the current index 'i' (middle character) is different from its immediate left character 's[i-1]'

- Symmetry Check: Ensure the character to the left and right of the middle character (at distances defined by charCount) are the same as s[i-1]

- If all conditions are met, increment 'count' and 'charCount'

Time and Space complexity analysis

Step 1: Count substrings with all identical characters

• The outer 'while' loop runs 'n' times in the worst case, where 'n' is the length of the string
• The inner 'while' loop runs as long as consecutive characters are the same. Each iteration of the inner loop increments 'i', so each character is processed only once.
• Therefore, the total number of operations in this step is proportional to 'n'

The time complexity of step one is O(n)

Step 2: Count substrings with one different middle character

• The outer 'for' loop runs 'n-1' times
• The inner 'while' loop checks characters symmetrically around the middle character. In the worst case, it can iterate up to half the length of the string for each character in the outer loop.
• However, each character is part of at most one such symmetric substring, so the inner loop's total number of iterations across all outer loop iterations is also proportional to 'n'.

So the time complexity of step 2 is O(n)

Combined time complexity:

Both steps individually have a time complexity of O(n). Therefore, the combined time complexity of the 'substrCount' function is: O(n)

Space complexity:

Step 1: Count substrings with all identical characters

The function uses a few integer variables ('count', 'i', 'charCount')

These variables use constant space, O(1)

Step 2: Count substrings with one different middle character

The function uses a few integer variables ('i', 'charCount')

These variables use constant space, O(1)

Total space complexity: O(1)

Thank you for taking the time to read this article.