Special String Again

Sort by

recency

|

784 Discussions

|

  • + 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
    
  • + 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();

  • + 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;
    }
    
  • + 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;
    }
    
  • + 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;
    
    }