Problem Description

You need to find the total number of substrings in a given string where the first and last characters are the same.

Given a string s that contains only lowercase English letters (indexed starting from 0), count all possible substrings that begin and end with the same character.

A substring is defined as any contiguous sequence of characters within the string that is not empty.

For example, if s = "aba":

• Single character substrings: "a", "b", "a" (all begin and end with the same character)
• Two character substrings: "ab", "ba" (neither begins and ends with the same character)
• Three character substring: "aba" (begins and ends with 'a')
• Total count: 4

The solution uses a counting approach: for each character encountered while traversing the string, it keeps track of how many times that character has appeared so far. Each occurrence of a character can form valid substrings with all its previous occurrences (including itself as a single-character substring), so the count for that character is added to the answer.

Intuition

When we need to count substrings that begin and end with the same character, let's think about what happens when we encounter a character while traversing the string.

Consider a character 'a' appearing at different positions in the string. If 'a' appears at positions i1, i2, i3, ..., then:

• The 'a' at position i1 forms 1 valid substring (itself)
• The 'a' at position i2 forms 2 valid substrings: itself and the substring from i1 to i2
• The 'a' at position i3 forms 3 valid substrings: itself, the substring from i1 to i3, and the substring from i2 to i3

The pattern becomes clear: when we encounter a character c that has already appeared k times before, this new occurrence can form valid substrings with each of the previous k occurrences, plus itself as a single-character substring. That's k + 1 new valid substrings.

This leads to the key insight: instead of checking all possible substrings (which would be O(n²)), we can simply keep a running count of how many times each character has appeared. When we see a character, we increment its count and add that count to our answer. This works because:

• The first occurrence of a character contributes 1 substring
• The second occurrence contributes 2 substrings
• The third occurrence contributes 3 substrings
• And so on...

This transforms the problem into a simple counting exercise that can be solved in a single pass through the string with O(n) time complexity.

Learn more about Math and Prefix Sum patterns.

Solution Approach

The implementation uses a hash table (or an array of size 26 for lowercase English letters) to track the count of each character as we traverse the string.

Here's how the algorithm works step by step:

1. Initialize data structures: Create a counter cnt (using Python's Counter class or a hash table) to store the frequency of each character encountered so far. Initialize the answer variable ans to 0.

2. Single pass traversal: Iterate through each character c in the string s.

3. Update character count: For each character c:

   • Increment its count: cnt[c] += 1
   • This new count represents how many times we've seen this character up to the current position

4. Add to answer: Add cnt[c] to the answer. This is the crucial step because:

   • If cnt[c] = 1 (first occurrence), it contributes 1 substring (itself)
   • If cnt[c] = 2 (second occurrence), it can form substrings with the first occurrence and itself, contributing 2 more substrings
   • If cnt[c] = k, it can form substrings with all k-1 previous occurrences plus itself, contributing k substrings

5. Return result: After processing all characters, return ans.

The beauty of this approach is its efficiency:

• Time Complexity: O(n) where n is the length of the string, as we only need one pass
• Space Complexity: O(1) since we only need to store counts for at most 26 lowercase letters (or O(k) where k is the size of the character set)

For example, with s = "abcab":

• 'a' at index 0: cnt['a'] = 1, add 1 to answer
• 'b' at index 1: cnt['b'] = 1, add 1 to answer
• 'c' at index 2: cnt['c'] = 1, add 1 to answer
• 'a' at index 3: cnt['a'] = 2, add 2 to answer (substrings "a" and "abca")
• 'b' at index 4: cnt['b'] = 2, add 2 to answer (substrings "b" and "bcab")
• Final answer: 1 + 1 + 1 + 2 + 2 = 7

Example Walkthrough

Let's walk through the algorithm with the string s = "ababa".

We'll track our character counts and running answer as we process each character:

Initial state:

• cnt = {} (empty counter)
• ans = 0

Step 1: Process 'a' at index 0

• Increment count: cnt['a'] = 1
• Add to answer: ans = 0 + 1 = 1
• Valid substrings ending here: "a" (1 substring)

Step 2: Process 'b' at index 1

• Increment count: cnt['b'] = 1
• Add to answer: ans = 1 + 1 = 2
• Valid substrings ending here: "b" (1 substring)

Step 3: Process 'a' at index 2

• Increment count: cnt['a'] = 2
• Add to answer: ans = 2 + 2 = 4
• Valid substrings ending here: "a" and "aba" (2 substrings)
  • The 'a' at index 2 can form substrings with the 'a' at index 0 and itself

Step 4: Process 'b' at index 3

• Increment count: cnt['b'] = 2
• Add to answer: ans = 4 + 2 = 6
• Valid substrings ending here: "b" and "bab" (2 substrings)
  • The 'b' at index 3 can form substrings with the 'b' at index 1 and itself

Step 5: Process 'a' at index 4

• Increment count: cnt['a'] = 3
• Add to answer: ans = 6 + 3 = 9
• Valid substrings ending here: "a", "aba", and "ababa" (3 substrings)
  • The 'a' at index 4 can form substrings with both 'a's at indices 0 and 2, plus itself

Final Result: 9

All valid substrings that begin and end with the same character:

1. "a" (index 0)
2. "b" (index 1)
3. "a" (index 2)
4. "aba" (indices 0-2)
5. "b" (index 3)
6. "bab" (indices 1-3)
7. "a" (index 4)
8. "aba" (indices 2-4)
9. "ababa" (indices 0-4)

The key insight: when we encounter the third 'a', it contributes 3 new valid substrings because it can pair with each of the 2 previous 'a's to form substrings, plus count itself as a single-character substring.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. The algorithm iterates through each character in the string exactly once, and for each character, it performs constant-time operations (incrementing the counter and adding to the answer).

The space complexity is O(|Σ|), where Σ is the character set. The Counter object stores at most one entry for each unique character that appears in the string. Since the problem deals with strings that could contain lowercase English letters, the maximum number of unique characters is 26, so |Σ| = 26. Therefore, the space complexity is O(26) = O(1) in terms of constant space for this specific constraint.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Counting Logic

Pitfall: Many developers initially think they need to explicitly find all substrings and check if their first and last characters match, leading to an O(n²) or O(n³) solution.

# Incorrect approach - brute force checking all substrings
def numberOfSubstrings_incorrect(s: str) -> int:
    count = 0
    n = len(s)
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            if substring[0] == substring[-1]:
                count += 1
    return count

Solution: Understand that when we encounter a character at position i, it can form valid substrings with all previous occurrences of the same character. The count at each step represents the number of valid substrings ending at the current position.

2. Off-by-One Error in Counting

Pitfall: Forgetting to count the single-character substring or incorrectly calculating the contribution of each character occurrence.

# Incorrect - forgetting to include the character itself
def numberOfSubstrings_wrong(s: str) -> int:
    char_count = Counter()
    total = 0
    for char in s:
        total += char_count[char]  # Missing the increment before adding
        char_count[char] += 1
    return total

Solution: Always increment the character count BEFORE adding to the total, ensuring each character contributes correctly (including single-character substrings).

3. Using Inefficient Data Structure

Pitfall: Using a list to track all positions of each character and then calculating distances, which unnecessarily complicates the solution.

# Overly complex approach
def numberOfSubstrings_complex(s: str) -> int:
    positions = defaultdict(list)
    total = 0
    for i, char in enumerate(s):
        positions[char].append(i)
        total += len(positions[char])
    return total

Solution: Simply maintain a count for each character. You don't need to track positions since we only care about the number of previous occurrences.

4. Memory Optimization Misconception

Pitfall: Trying to optimize memory by using an array of size 26 but making indexing errors.

# Error-prone array indexing
def numberOfSubstrings_array_error(s: str) -> int:
    counts = [0] * 26
    total = 0
    for char in s:
        counts[ord(char) - ord('a')] += 1
        total += counts[ord(char) - ord('A')]  # Wrong offset!
    return total

Solution: If using an array, be consistent with the character-to-index conversion. Using Counter() is cleaner and prevents such errors:

def numberOfSubstrings_correct(s: str) -> int:
    char_count = Counter()
    total = 0
    for char in s:
        char_count[char] += 1
        total += char_count[char]
    return total