Sort by

recency

|

784 Discussions

|

2 months ago+ 0 comments

I use a deque to keep track of previous counts to find the middle cases. I like this solution because there is a single loop while most other solutions have nested loops.

from collections import deque

# Complete the substrCount function below.
def substrCount(n, s):
    current_char = None
    total_count = 0
    char_count = 0
    count_deque = deque([0, 0], maxlen=2)

    for i in range(n):
        if s[i] == current_char:
            char_count += 1
        else:
            # check for middle chars
            if i >=3 and count_deque[1] == 1 and s[i-2-char_count] == current_char:
                
                middle_case_count = min([count_deque[0], char_count])
                total_count += middle_case_count
            total_count += sum(range(char_count+1))
            count_deque.append(char_count)
            current_char = s[i]
            char_count = 1
            
    if i >=3 and count_deque[1] == 1 and s[i-1-char_count] == current_char:
        middle_case_count = min([count_deque[0], char_count])
        total_count += middle_case_count
    total_count += sum(range(char_count+1))
    return total_count

3 months ago+ 0 comments

import { WriteStream, createWriteStream } from 'fs'; import { stdin, stdout } from 'process';

// Function to count special substrings function substrCount(n: number, s: string): number { let count = 0;

// Count all uniform substrings
let i = 0;
while (i < n) {
    let length = 1;
    while (i + 1 < n && s[i] === s[i + 1]) {
        length++;
        i++;
    }
    count += (length * (length + 1)) / 2;
    i++;
}

// Count all substrings of the form where one character is different in the middle
for (let i = 1; i < n - 1; i++) {
    let length = 0;
    while (i - length >= 0 && i + length < n && s[i - length] === s[i + length] && s[i - length] !== s[i]) {
        count++;
        length++;
    }
}

return count;

}

// Main function to handle input and output function main() { const inputLines: string[] = [];

stdin.setEncoding('utf-8');
stdin.on('data', (chunk: string) => {
    inputLines.push(...chunk.trim().split('\n'));
});

stdin.on('end', () => {
    const outputStream: WriteStream = createWriteStream(process.env['OUTPUT_PATH'] || '/dev/stdout');

    const n: number = parseInt(inputLines[0].trim(), 10);
    const s: string = inputLines[1].trim();

    const result: number = substrCount(n, s);

    outputStream.write(result + '\n');
    outputStream.end();
});

}

main();

3 months ago+ 0 comments

standard dynamic programming O(n) algo

long substrCount(int n, const string& s) {
    long total = 0;
    vector<vector<int>> con1(n + 1, vector<int>(26));
    vector<int> con2(n + 1, -1);
    for (int i = 1; i <= n; ++i) {
        con1[i][s[i-1] - 'a'] = con1[i-1][s[i-1]-'a'] + 1;
        total = total + con1[i][s[i-1]-'a'];
    }
    for (int i = 3; i <= n; ++i) {
        if (s[i-1] != s[i-2] and s[i-1] == s[i-3]) con2[i] = 3;
        else if (s[i-1] == s[i-2] and con2[i-1] != -1 and i-con2[i-1]-1 > 0 and s[i-con2[i-1]-2] == s[i-1]) {
            con2[i] = con2[i-1] + 2;
        }
        if (con2[i] != -1) ++total;
    }
    return total;
}

4 months ago+ 0 comments

function substrCount(n, s) {

    let totalSpecialStrings = 0;

    for (let i = 0; i < n; i++) {
				
        // find consecutive matches
        let start = i;
								
        while (s[i] == s[i + 1] && i <= n) {
            i++;
            totalSpecialStrings++;
        }
        let end = i;

        //find substrings in consecutive matches of size 3 or more
        let sameChars = s.substring(start, end + 1);
        let seqSize = 3;
				
        while (seqSize <= sameChars.length) {
            totalSpecialStrings += sameChars.length - seqSize + 1;
            seqSize++;
        };

        // find palindrome sandwhich
        let prevCharIndex = i - 1;
        let nextCharIndex = i + 1;
        let prevChars = s.substring(prevCharIndex, i);
        let nextChars = s.substring(i + 1, nextCharIndex + 1);
				
        while (prevChars == nextChars) {
            totalSpecialStrings++;
            prevCharIndex--;
            nextCharIndex++;
            prevChars = s.substring(prevCharIndex, i);
            nextChars = s.substring(i + 1, nextCharIndex + 1);

        }
    }
    return totalSpecialStrings + n;
}

6 months ago+ 0 comments

Cpp solution - all test cases passed.

/*To approach this problem, its crucial to understand how to fetch all palindromes from a string
as it is a variation of that problem*/

long substrCount(int n, string s) {

    /*Conditons for palindrome:
    A.- All of the characters are the same, e.g. aaa.
    B.- All characters except the middle one are the same, e.g. aadaa.
    */
    long palCount = 0; 

    /*Two "pointers" in order to slide left and right to find palindrome*/
    int rPos = 0, lPos = 0;

    //Main loop that will traverse string
    for (int i = 0; i < n; i++)
    {
        //We set both "pointers" to i
        rPos = lPos = i;
        char letter = s[i];

        /*If where we are pointing, is within the interval of string and "pointers" value are the same
        that means that we found a palindrome, however, we must check if palindrome fullfill conditons A and B */
        while ((rPos < n) && (lPos >= 0) && (s[rPos] == s[lPos]))
        {

            //Check if all letters are the same, or first letter
            if (s[rPos] == letter)
            {
                palCount++;
                rPos++;
                lPos--;
            }
            else
            {
                /*If letters differ, then we have to check if we already moved our "pointers" from the
                starting position "i"*/
                if (rPos - i <= 1)
                {
                    /*This means we have not done that, so this means that we are in the first iteration of i
                    we increase the count and set the new letter to upper and lower limit of our first palindrome of
                    lenght > 1*/
                    palCount++;

                    /*As you can see here, a new letter is set, this means that for all of the next iterations,
                    all letters must match new letter*/
                    letter = s[rPos];
                    rPos++;
                    lPos--;
                }  
                else
                {
                    /*No match, so we break and "i" is incremented*/
                    break;
                }
            }
            
        }

        //Same process but for substrings of pair size
        rPos = i + 1;
        lPos = i;
        letter = s[i];

        /*If we have abba string, we will start evaluating substr(0,2) -> "ab",
        in this case, this while loop has a slight modification than the previous one, 
        here, we just have to make sure that all of the letters are the same*/
        while ((rPos < n) && (lPos >= 0) && (s[rPos] == s[lPos]) && (s[rPos] == letter))
        {
            palCount++;
            rPos++;
            lPos--;
        }

    }

    return palCount;

}

Sort by

|

784 Discussions

|

Cpp solution - all test cases passed.

Cookie support is required to access HackerRank