Substrings That Begin and End With the Same Letter

Substrings That Begin and End With the Same Letter - Problem

Hash Table Math String Counting Prefix Sum Medium

You are given a 0-indexed string s consisting of only lowercase English letters. Return the number of substrings in s that begin and end with the same character.

A substring is a contiguous non-empty sequence of characters within a string.

Input & Output

Example 1 — Basic Case

$ Input: s = "abaca"

› Output: 8

💡 Note: Character 'a' appears 3 times: forms 3×4÷2=6 substrings. Characters 'b' and 'c' each appear once: each forms 1 substring. Total: 6+1+1=8

Example 2 — Single Character

$ Input: s = "aa"

› Output: 3

💡 Note: Character 'a' appears 2 times: forms 2×3÷2=3 substrings ("a", "a", "aa")

Example 3 — All Different

$ Input: s = "abc"

› Output: 3

💡 Note: Each character appears once: each forms 1 substring. Total: 1+1+1=3

Constraints

1 ≤ s.length ≤ 10⁵
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String with lowercase letters

Process

Count character frequencies and apply formula

Output

Total number of valid substrings

Key Takeaway

🎯 Key Insight: Each character contributes n×(n+1)/2 substrings where n is its frequency

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is that for n occurrences of any character, we can form exactly n×(n+1)/2 substrings that begin and end with that character. Best approach is frequency counting with mathematical formula. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Character Frequency Count	O(n)	O(1)	Count each character's frequency, then calculate combinations using mathematical formula
Brute Force - Check All Substrings	O(n³)	O(1)	Generate every possible substring and count those with matching first and last characters

Character Frequency Count — Algorithm Steps

Count frequency of each character
For each character, calculate n×(n+1)/2 combinations
Sum all combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how many times each character appears

Apply Formula

For n occurrences: n×(n+1)/2 substrings

Sum Results

Add up all character contributions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s) {
    // Count frequency of each character (assuming lowercase letters only)
    int freq[26] = {0};
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        freq[s[i] - 'a']++;
    }
    
    // Calculate total substrings
    int total = 0;
    for (int i = 0; i < 26; i++) {
        int count = freq[i];
        if (count > 0) {
            // For n occurrences, we can form n*(n+1)/2 substrings
            total += count * (count + 1) / 2;
        }
    }
    
    return total;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies, then O(26) to calculate combinations

✓ Linear Growth

Space Complexity

O(1)

Hash map stores at most 26 characters (constant space)

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Character Frequency Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler