Search code examples
arraysstringalgorithmsubstring

Find the number of substrings of this string that start and end with different characters

Find the number of substrings of this string that start and end with different characters. If the same substring appears multiple times in S, it is to be counted multiple times.

What approach should i follow. My solution is not optimised

Solution

  • There are P=n*(n+1)/2 possible substrings of the string with length n (including 1-length ones)

    Find counts for every distinct character in the string.

    banana => {'b':1; 'a':3; 'n':2}

    If some char c occurs k times, there are k*(k+1)/2 substrings that start and end with this character c (including 1-length ones again!) - so we must subtract this quantity from overall P.
    Repeat for other chars.

    21 - 1 -6 - 3 = 11

    If substring length should be >=2, then we have to use P=n*(n-1)/2 and k*(k-1)/2 formulas

    15  -0 -3 -1 = 11

    Surprisingly, result is the same ;)