substrings-that-begin-and-end-with-the-same-letter

< Previous 　　　　　　　　　　　　　　　　 Next >

2083. Substrings That Begin and End With the Same Letter (Medium)

Related Topics

[Hash Table] [Math] [String] [Counting] [Prefix Sum]

Hints

Hint 1

In the string "abacad", the letter "a" appears 3 times. How many substrings begin with the first "a" and end with any "a"?

Hint 2

There are 3 substrings ("a", "aba", and "abaca"). How many substrings begin with the second "a" and end with any "a"? How about the third?

Hint 3

2 substrings begin with the second "a" ("a", and "aca") and 1 substring begins with the third "a" ("a").

Hint 4

There is a total of 3 + 2 + 1 = 6 substrings that begin and end with "a".

Hint 5

If a character appears i times in the string, there are i * (i + 1) / 2 substrings that begin and end with that character.