In this HackerRank Special String Again Interview preparation kit problem you need to Complete the substrCount function in the editor below. It should return an integer representing the number of special substrings that can be formed from the given string.


HackerRank Special String Again interview preparation kit solution


Problem solution in Python programming.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the substrCount function below.
def substrCount(n, s):
    tot = 0
    count_sequence = 0
    prev = ''
    for i,v in enumerate(s):
        # first increase counter for all seperate characters
        count_sequence += 1
        if i and (prev != v):
            # if this is not the first char in the string 
            # and it is not same as previous char, 
            # we should check for sequence x.x, xx.xx, xxx.xxx etc
            # and we know it cant be longer on the right side than
            # the sequence we already found on the left side.
            j = 1
            while ((i-j) >= 0) and ((i+j) < len(s)) and j <= count_sequence:
                # make sure the chars to the right and left are equal
                # to the char in the previous found squence
                if s[i-j] == prev == s[i+j]:
                    # if so increase total score and step one step further out
                    tot += 1
                    j += 1
                else:
                    # no need to loop any further if this loop did 
                    # not find an x.x  pattern
                    break
            #if the current char is different from previous, reset counter to 1
            count_sequence = 1  
        tot += count_sequence            
        prev = v
    return tot

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    s = input()

    result = substrCount(n, s)

    fptr.write(str(result) + '\n')

    fptr.close()


Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    static class Point {
    public char key;
    public long count;

    public Point(char x, long y) {
        key = x;
        count = y;
    }
}

// Complete the substrCount function below.
static long substrCount(int n, String s) {
    s = s + " ";
    ArrayList<Point> l = new ArrayList<Point>();
    long count = 1;
    char ch = s.charAt(0);
    for(int i = 1; i <= n ; i++) {
        if(ch == s.charAt(i))
            count++;
        else {
            l.add(new Point(ch, count));
            count = 1;
            ch = s.charAt(i);
        }
    }
    count = 0;
    if(l.size() >= 3) {   
        Iterator<Point> itr = l.iterator();
        Point prev, curr, next;
        curr = (Point)itr.next();
        next = (Point)itr.next();
        count = (curr.count * (curr.count + 1)) / 2;
        for(int i = 1; i < l.size() - 1; i++) {
            prev = curr;
            curr = next;
            next = itr.next();
            count += (curr.count * (curr.count + 1)) / 2;
            if(prev.key == next.key && curr.count == 1)
                count += prev.count > next.count ? next.count : prev.count;
        }
        count += (next.count * (next.count + 1)) / 2;
    } else {
        for(Point curr:l){
            count += (curr.count * (curr.count + 1)) / 2;
        }
    }
    return count;
}

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        String s = scanner.nextLine();

        long result = substrCount(n, s);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}


Problem solution in C++ programming.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,c,i=0,j,ans=0;
    cin>>n;

    string s;
    cin>>s;

    int same_char_count[n]={0};

    while(i<n) {
        j=i+1,c=1;
        while(j<n && s[i]==s[j]) {
            ++j,++c;
        }

        //total substrings which have all same char(s)
        ans+=(c*(c+1))>>1;
        same_char_count[i]=c;
        i=j;
    }

    for(j=1;j<n-1;++j) {
        if(s[j]==s[j-1]) {
            same_char_count[j] = same_char_count[j-1];
        }

        //odd length substr(s) which has middle element diiferent
        if(s[j-1]==s[j+1] && s[j]!=s[j-1]) {
            ans += min(same_char_count[j-1], same_char_count[j+1]);
        }
    }
    cout<<ans<<endl;

    return 0;
}