Count Substrings Starting and Ending with Given Character

Count Substrings Starting and Ending with Given Character - Problem

You are given a string s and a character c. Return the total number of substrings of s that start and end with c.

A substring is a contiguous sequence of characters within a string.

Input & Output

Example 1 — Basic Case

$ Input: s = "abaca", c = "a"

› Output: 6

💡 Note: The substrings starting and ending with 'a' are: "a" (position 0), "a" (position 2), "a" (position 4), "aba", "abaca", and "aca". Total count is 6.

Example 2 — No Matches

$ Input: s = "abc", c = "z"

› Output: 0

💡 Note: Character 'z' doesn't appear in string "abc", so no substrings can start and end with 'z'.

Example 3 — Single Character

$ Input: s = "a", c = "a"

› Output: 1

💡 Note: Only one substring "a" exists, and it starts and ends with 'a'.

Constraints

1 ≤ s.length ≤ 10⁵
c is a single lowercase English letter
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String s and target character c

Process

Count occurrences of c and apply combination formula

Output

Total number of valid substrings

Key Takeaway

🎯 Key Insight: When a character appears n times, you can form exactly n×(n+1)/2 substrings that start and end with it

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that if character c appears n times in the string, we can form exactly n*(n+1)/2 valid substrings. This includes each single occurrence plus all possible combinations between any two positions. Best approach is the mathematical formula with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check all possible substrings to see if they start and end with character c
Mathematical Formula	O(n)	O(1)	Count occurrences of character c, then use combination formula n*(n+1)/2

Brute Force — Algorithm Steps

Generate all possible substrings using nested loops
For each substring, check if first and last characters equal c
Count valid substrings

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Use nested loops to create all possible substrings

Check Ends

For each substring, verify first and last characters

Count Matches

Increment counter when both ends match character c

Code -

solution.c — C

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

int solution(char* s, char c) {
    int count = 0;
    int n = strlen(s);
    
    // Check all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Check if substring starts and ends with c
            if (s[i] == c && s[j] == c) {
                count++;
            }
        }
    }
    
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Two nested loops to generate O(n²) substrings, plus O(n) to check each substring

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables for counting

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 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

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler