Implemented your logic in Java. Had to tweak the code to optimise it and also reduced it to 2 passes

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

can youb explain me 3rd pass

Smart solution. Thank you!

i didn't understand here, for i in range(1, len(l) - 1): f l[i - 1][0] == l[i + 1][0] and l[i][1] == 1: ans += min(l[i - 1][1], l[i + 1][1]) please explain me..!!

Why this approach return 11 for input 'cbbabbc' as an example ?

Correct answer should be 12 in this case. (c, b, b, a, b, b, c, bb, bb, bab, bbabb, cbbabbc)

I think there is a bug in 3rd testCase as its only checking i-1, i and i+1.

There should be a recursive way to keep check n-1 and n+1 terms until they are matching or something like that, then start taking min of each of those.

May I know why this works?

(i[1] * (i[1] + 1)) // 2

wow how did you think of that 0.o

No Need for the // in ans += (i[1] * (i[1] + 1)) // 2 as i[1] will always be greater than 1 and hence i[1]+1 will be even when i[1] is odd and vice-versa. So this formula yeilds only integer results.

very nice!

Thanks for the logic and style, I'm sure many have learned from it! Following the same logic described, I have the same solution written in C++ for anyone who wanted to see it in the language

Here it is:

long substrCount(int n, string s) {

long count = 0;
vector<std::pair<char, int>> frequencies;
int i=0, j=0;

for ( i = 0; i < n; i++)
{
    for( j = i+1; j < n; j++)
    {
        if (s[j] == s[i])
            continue;
        else
            break;
    }
    frequencies.push_back(std::make_pair(s[i],j-i));
    i = j-1;
}

for (i=0; i < frequencies.size(); i++)
    count += (frequencies[i].second+1) * frequencies[i].second / 2;

for (i=1; i < frequencies.size()-1; i++)
{
    if ( frequencies[i].second == 1 && frequencies[i-1].first == frequencies[i+1].first)
        count += min(frequencies[i-1].second, frequencies[i+1].second);
}

return count;

}

Nice solution! One thing that condenses the code a bit is using itertools.groupby to turn the logic of the first loop into a 1 liner:

l = [(ch, len(list(g))) for ch, g in groupby(s)]

Thanks!

For those who doesn't understand this line,

for i in l: ans += (i[1] * (i[1] + 1)) / 2

its from a formula n(n+1)/2 which give the sum of all term, like n = 5, 1+2+3+4+5 = 5(5+1)/2 = 15.

Its used because if you have "aaaa" , you can have "a,a,a,a", "aa,aa,aa", "aaa,aaa" and "aaaa", we can see the partern of 4,3,2,1 groups, so in this case there's 15 groups!

excellent solution - there is a detailed explanation on this page if anyone else is interested

Wow nice solution. I didn't understand the intuition behind this line: ans += (i[1] * (i[1] + 1)) i.e if all chars are same. Can anyone comment on that ?

Appears that RLE (run length encoding) compression is the consensus; I did so too. My implementation ran through the list twice instead - just makes the code all the more clear.

Nice solution, thanks!!

I feel this is a very complicated answer. You can solve this problem in 10 lines, using the same logic as you would manually do when you solve it by hand : For each index i in the string, I create a cursor k that starts from i and goes forward until it meets a different letter than s[i] at s[i+k]. Then I check if the string starting from s[i] centrered on s[i+k] could be a palindrome.

I put my code in this discussion

I can't quite figure out the formula in the 2nd pass

ans += (i[1] * (i[1] + 1)) // 2

How is this derived? Emprically I understand that it is correct. But I can't quite understand why.

    static int palindromHalfLength(int i, String s) {
        int step = 1;
        char palChar = s.charAt(i-1);
        while (i-step>=0 && i+step<s.length()
                && s.charAt(i-step) == palChar
                && s.charAt(i+step) == palChar) step++;

        return step-1;
    }
    // Complete the substrCount function below.
    static long substrCount(int n, String s) {
        if (s.length() == 0) return 0;
        long res = 1;
        int countSimChar = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i-1) == s.charAt(i)) {
                countSimChar++;
            }  else {
                res += palindromHalfLength(i, s);
                countSimChar = 1;
            }
            res += countSimChar;
        }
        return res;
    }

If there are k similar characters in a raw, number of palindroms will be 1+2+..+k; If current character differs from the prvious one it might also be a palindrom, and half length of the palindrom would be the number of palindroms: aaacaaa -> half length is 3 and there are 3 palindroms: aca, aacaa, aaacaaa

Simplified way of writing 1st pass, no count, cur required:

for i in range(n):
	if not l or s[i] != s[i-1]:
		l.append((s[i],1))
		continue
	l[-1] = (s[i],(l[-1][1] + 1))

C# Code:

I passed 3 test cases but when I click on submit it doesn't pass any other. I can't even debug as the data is very large and I can only feed 40kb in the input field. Please help me!

Thanks.

long count = 0;
        string tempStr;
        for(int i = 0; i < n - 1; i++){
            for(int j = 2; j <= n - i; j++){
                tempStr = s.Substring(i,j);
                int flag = 0;
                int testStr = tempStr[0];
                int x = 0;
                int y = tempStr.Length - 1;
                Console.WriteLine(tempStr);
                while(x < y){
                    if(tempStr[x] == testStr && tempStr[y] == testStr){
                        Console.WriteLine(tempStr[x] + " " + tempStr[y]);
                        x++;
                        y--;
                    }
                    else{
                        flag = 1;
                        break;
                    }
                }
                Console.WriteLine(flag);
                if(flag == 0)
                    count++;
            }
        }

        return count + n;

Nice solution :)

Similar solution by using groupby() function:

 def substrCount(n, s):
                 import itertools as it
                if n == 1:
                        return 1      
                s = [list(g) for k, g in it.groupby(s)]
                res = sum([int(len(i)*(len(i)+1)/2) for i in s])

                for i in range(len(s)):
                        if i == 0 or i == len(s)-1 or len(s[i]) > 1 :
                                continue

                        if s[i-1][0] == s[i+1][0]:
                                res+= min(len(s[i-1]), len(s[i+1]))
                return res

Here's a rendition that made a bit more sense to me. The second pass uses the "nth triangle number" https://math.stackexchange.com/questions/593318/factorial-but-with-addition

def substrCount(n, s):

        counts = []

        for i in range(len(s)):
                if counts == []:
                        counts.append([s[i], 1])
                elif s[i] == counts[-1][0]:
                        counts[-1][1] = counts[-1][1] + 1
                else:
                        counts.append([s[i], 1])

        ans = 0
        for pair in counts:
                ans += pair[1] * (pair[1] + 1) / 2

        for i in range(len(counts) - 2):
                if counts[i + 1][1] == 1 and counts[i][0] == counts[i + 2][0]:
                        m = min(counts[i][1], counts[i + 2][1])
                        ans += m

        return int(ans)

Here's my implementation your logic with 2 passes:

def substrCount(n, s):
    
    prevChar = s[0]
    count = 1
    allChars = []
    res = 0 

    for c in s[1:]:
        if (c == prevChar):
            count += 1
        else:
            allChars.append((prevChar, count))
            res += ((count) * (count + 1)) // 2
            count = 1
            prevChar = c
    
    allChars.append((prevChar, count))
    res += ((count) * (count + 1)) // 2

    for i, val in enumerate(allChars[1:len(allChars)-1], start=1):
        left, right = allChars[i-1], allChars[i+1]
        if ((val[1] == 1) and (left[0] == right[0])):
            res += min(left[1], right[1])
            
    return res

I programmed like a hell but turned out this much easy. Thank you!

First pass can be done without using second variable 'cur'

 l = []
count = 1
for i in range(len(s)):
    try:
        if s[i] == s[i+1]:
            count+=1
        else:
            l.append((s[i],count))
            count = 1
    except:
        l.append((s[i],count))
ans = 0

I have done in similar way considering a dict.Can u please explain the 3rd pass in detail(logic)

great approach

Here is a single pass implemetation of the same logic....

def substrCount(n, s):
    l = []
    count = 0
    cur = None
    ans =0
    s_no = 0

    for i in range(n):
        if s[i] == cur:
            count += 1
        else:
            if cur is not None:
                l.append((cur, count))
    
                ans += (count * (count+1))//2
                s_no +=1 
    
                if s_no>=3:
                   if l[s_no - 3][0] == l[s_no-1][0] and l[s_no-2][1] == 1:
                        ans += min(l[s_no-3][1], l[s_no-1][1]) 
    
            cur = s[i]
            count = 1
    
    l.append((cur, count))
    
    ans += (count * (count+1))//2
    s_no+=1

    if s_no>=3:
        if l[s_no - 3][0] == l[s_no-1][0] and l[s_no-2][1] == 1:
            ans += min(l[s_no-3][1], l[s_no-1][1])

    return ans

I pretty much had the same solution, in two passes and with a few minor differences. in c++:

struct x {
    char c;
    int n;
};

long substrCount(int n, string s) {
    long total = 0;
    vector<x> table;

    for (int i = 0; i < s.length();) {
        char c = s[i];
        int len = 0;
        while (len + i < s.length() && s[i + len] == c)
            ++len;
        table.push_back({c, len});
        i += len;
    }
    for (int i = 0; i < table.size(); ++i) {
        total += (table[i].n * (table[i].n + 1)) / 2;
        if (table[i].n == 1
                && i > 0 && i < table.size() - 1
                && table[i - 1].c == table[i + 1].c) {
            total += min(table[i - 1].n, table[i + 1].n);
        }
    }
    return total;
}

That is wonderful code!

Can anyone explain me 2nd & 3rd pass?

I have explained in detail the complete logic and program for beginners while intermediates can just read the logic part to get the idea. The logic is faster than using regex method by 5% and the complexity is O(n). I have used recursions. The link to the github page is here.

The raw code is here,

# Complete the substrCount function below.
def count_centered(s,i,j,length,n):
    if (i < n-1) and (j > 0) and (s[i+1] == s[j-1]) and (s[i+1] == s[i]):
        return count_centered(s,i+1,j-1,length+1,n)
    else:
        return length + 1

def count_same(s,i,length,n):
    if (i < n-1) and (s[i+1] == s[i]):
        return count_same(s,i+1,length+1,n)
    else:
        return (length*(length + 1)/2)-1,i

def substrCount(n, s):
    count = 1
    i = 1
    while i < n:
        if s[i] == s[i-1]:
            temp,i = count_same(s,i,2,n)
            count += temp
        elif (i > 1) and s[i] == s[i-2]:
            count += count_centered(s,i,i-2,1,n)
        else:
            count += 1
        i+= 1
            
    return int(count)

Thank you for the solution! I've implemented it similarly in C#:

    static long substrCount(int n, string s) {
        int result = 0; 
        
        // Gather sequences of characters into a list of tuples.
        List<(char, int)> sequences = new List<(char, int)>();
        int firstCharInSequence = 0;
        for (int i = 1; i < n; i++) {
            if (s[i] != s[i-1]) {
                // Save the sequence to our list
                sequences.Add((s[i-1], i - firstCharInSequence));

                // Reset the counters
                firstCharInSequence = i;
            }
        }
        // Add the remainder
        sequences.Add((s[n-1], n - firstCharInSequence));        
        // now e.g. for aabaa we have a list of ('a', 2), ('b', 1), ('a', 2).
				
        // Second pass - add all repeated sequences of chars into the total count
        foreach (var seq in sequences) 
            result += seq.Item2 * (seq.Item2 + 1) / 2; 
            // triangular number sequence
        

        // Third pass - account for all palindromes with a different char in the middle
        int j = 0;
        while (j < sequences.Count - 2) {
            // We're moving the window of 3 numbers, from left to right.
            var left = sequences[j];
            var center = sequences[j+1];
            var right = sequences[j+2];
            
            // If the characters are the same on the sides,
            // and if there's only one character in the middle
            // Then count the widest substring, and all narrower ones.
            // e.g. aaa_aaa gives us 3 substrings: aaa_aaa, aa_aa, a_a. 
            if (left.Item1 == right.Item1 && center.Item2 == 1)
                result += Math.Min(left.Item2, right.Item2);
            
            j++; // Move the window one position to the right
        }
        
        return result;
    }

great solution! I implemented it in C++ Cheers!

I do not understand why in the 3rd pass is ans+=min(l[i - 1][1], l[i + 1][1]) and not the summatory of min f.e in aaabaaa the possible ones aren't aba aabaa aaabaaa ??? whith your code is only aaabaaa

I've tried to understand the algorithm at first place by just reading your 3 steps description, but I fail.

Thanks for you code (I knew it's bad not thinking by myself), but without the code I cannot make it. It's genious solution.

Hi! can you explain me why this formula: (i[1] * (i[1] + 1)) // 2 works?

Maybe is related with combinatorics, the thing is that I don't understand that.

Thank you for your time

converted to java using your logic a simplified

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

class point { char ch; int count; point(char ch,int count) { this.ch=ch; this.count=count; } } public class Solution {

// Complete the substrCount function below.
static long substrCount(int n, String s) 
{
    char ch=' ';
    int count=1;

    ArrayList<point> ar = new ArrayList<point>();

    for(int i=0;i<n;i++)
    {
        if(s.charAt(i)==ch)
        {
            count++;
        }
        else
        {
            ar.add(new point(ch,count));
            ch=s.charAt(i);
            count=1;
        }
    }
    ar.add(new point(ch,count));

    long ans=0;

    for(int i=0;i<ar.size();i++)
    {
        int k= ar.get(i).count;
        ans+=(k*(k+1))/2;
    }

    //  System.out.println(ans);
    for(int i=1;i<ar.size()-1;i++)
    {
        if(ar.get(i-1).ch==ar.get(i+1).ch && ar.get(i).count==1)
        {
            ans+=Math.min(ar.get(i-1).count,ar.get(i+1).count);
        }
    }

    return ans-1;

}

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();
}

}

Thanks for the simple solution. I especially found the 3rd pass to be verify useful (that was the 'aha' moment for me):

if l[i - 1][0] == l[i + 1][0] and l[i][1] == 1:

ans += min(l[i - 1][1], l[i + 1][1])

fucking good :)

here is java

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 {

// Complete the substrCount function below.
//1 3 6 10
static long substrCount(int n, String s) {
    char[] ch = new char[1000000];
    char tempCh = s.charAt(0);
    int[] num = new int[1000000];
    ch[0] = tempCh;
    num[0] = 1;
    int index = 0;
    int result = 0;
    for(int i = 1; i<s.length(); i++){
        if(tempCh == s.charAt(i)){
            num[index]++;
        } else{
            tempCh = s.charAt(i); 
            index++;
            num[index] = 1;
            ch[index] = s.charAt(i);
        }
    }
    for(int i = 0; i<index+1; i++){
        result += (num[i] * (num[i]-1))/2 + num[i];
    }
    for(int i = 1; i<index; i++){
        if(ch[i-1] == ch[i+1] && num[i] == 1){
            result += num[i-1] > num[i+1] ? num[i+1] : num[i-1];
        }
    }
    return result;
}

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();
}

}

Thanks! I didn't think of first organising into tuple array

c++ code

long substrCount(int n, string s) {

long ans=0;
vector<pair<char,int>>v;
int occur=1;
for(int i=1;i<n;i++)
{
    if(s[i]==s[i-1])
    occur++;
    else
    {
        v.push_back({s[i-1],occur});
        occur=1;
    }
}
v.push_back({s[n-1],occur});

for(int i=0;i<v.size();i++)
{
    ans+= (v[i].second * (v[i].second+1))/2;

    if(i!=0 && i!=v.size()-1)
    {
        if(v[i].second==1 && v[i-1].first==v[i+1].first)
        ans+= min(v[i-1].second,v[i+1].second);
    }
}

return ans;

}

return 0;

}

I think people should post their pseudocode and explain how it might work to pass all test cases

Sir, can you please explain about the formula you used in second pass.

This was alot of help thanks. got really confused at one point, becuase i thought the 2 substrings on the sides of the single character substring had to be the same number of chars. thanks :D

very smart approach to reduce the string to another structure

Thank you!

nice thank u

Great. Super understandable

Like! Same in java :

static long substrCount(int n, String s) {

    long result = 0;
    int count = 1;
    String temp = null;

    ArrayList<String> keys = new ArrayList<>();
    ArrayList<Integer> values = new ArrayList<>();

    // 1st pass
    for (String c : s.split("")) {
        if (c.equals(temp))
            count++;
        else {
            if (temp != null) {
                keys.add(temp);
                values.add(count);
            }
            count = 1;
            temp = c;
        }
    }

    keys.add(temp);
    values.add(count);

    // 2nd pass
    for (int value : values) {
        result += value * (value + 1) / 2;
    }

    // 3d pass
    for (int i = 1; i < values.size() - 1; i++) {
        if (keys.get(i - 1).equals(keys.get(i + 1)) && values.get(i) == 1)
            result += Math.min(values.get(i - 1), values.get(i + 1));
    }

    return result;
}

Cool! Here's a Ruby version:

def substr_count(n, s)
  comp = s.chars.each_with_object([]) do |c, acc|
    if !acc.empty? && acc.last[0] == c
      acc[-1] = [c, acc.last[1] + 1]
    else
      acc << [c, 1]
    end
  end

  count = comp.map { |_c, l| l * (l + 1) / 2 }.sum

  (1...(comp.length - 1)).each do |i|
    count += [comp[i - 1][1], comp[i + 1][1]].min if comp[i - 1][0] == comp[i + 1][0] && comp[i][1] == 1
  end
  count
end


n = gets.to_i
s = gets.chomp
puts substr_count(n, s)

One pass solution with backtracking, collecting all valid palindromes. Passes all tests.

def substrCount(n, s):
    # print('---', s)
    subs = []
    for i, l in enumerate(s):
        # collect all single chars
        subs.append(l)

        if i > 0:
            # collect all substrings of same chars behind i
            j = i - 1
            sub = l
            while j >= 0 and s[j] == l:
                sub += s[j]
                subs.append(sub)
                j -= 1

            # collect all substrings where middle char is different 
            # and all chars on left and right are the same
            j = i - 1
            if s[j] != l:                
                k = i + 1
                sub = l
                while j >= 0 and k < n and s[j] == s[k]:
                    if j+1 < i and s[j] != s[j+1]:
                        break

                    sub = f'{s[j]}{sub}{s[k]}'
                    subs.append(sub)
                    j -= 1
                    k += 1

    # print(subs)

    return len(subs)

Here is javascript code:

function substrCount(n, s) { let count = 0; const arr = s.split(''); const tuple = [[arr[0], 1]];

for (let i = 1; i < arr.length; i++) {
    const element = arr[i];
    if (element == tuple[tuple.length - 1][0]) {
        tuple[tuple.length - 1][1]++
    } else {
        tuple.push([element, 1]);
    }
}

for (const element of tuple) {
    count += (element[1] * (element[1] +1)) /2
} 

for (let i = 1; i < tuple.length - 1; i++) {
    const element = arr[i];
    if (tuple[i - 1][0] == tuple[i + 1][0] && tuple[i][1] == 1) {
        const min = tuple[i - 1][1] > tuple[i + 1][1] ? tuple[i + 1][1] :  tuple[i - 1][1]
        count += min;
    } 

}
return count;

}