Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Count Substrings Starting and Ending with Given Character solution and explanation

MediumCountingMathString5 min read50.5% acceptanceUpdated 9 Apr 2026
Practise Count Substrings Starting and Ending with Given Character
11:39
Count Substrings Starting and Ending with Given Character | Leetcode 3084 | codestorywithMIKcodestorywithMIK · 11:39 · 5K viewsWatch on YouTube
9 more videos on this problem
  1. Count Substrings Starting and Ending with Given Character | Leetcode 3084 | codestorywithMIKcodestorywithMIK · 11:39 · 5K views
  2. 3084. Count Substrings Starting and Ending with Given Character | Math | Sum of n Natural NumbersAryan Mittal · 5:57 · 3K views
  3. Leetcode 3084. Count Substrings Starting and Ending with Given CharacterElite Code · 14:37 · 1K views
  4. Leetcode 3084: Count Substrings Starting and Ending with Given CharacterAlgorithms Casts · 9:54 · 456 views
  5. Leetcode | 3084. Count Substrings Starting and Ending With Given Characters | Medium | JavaDeveloper Docs · 3:55 · 441 views
  6. 3084. Count Substrings Starting and Ending with Given Character || Leetcode Weekly Contest 389Ashish Kumar · 5:36 · 397 views
  7. 3084. Count Substrings Starting and Ending with Given Character (Leetcode Medium)Programming Live with Larry · 2:58 · 220 views
  8. Leetcode # 3084 Count Substrings Starting and Ending with Given Character (Python)Sumanshu Nankana · 17:59 · 49 views
  9. Leetcode 3084 - Count Substrings Starting and Ending with Given Character (Leetcode Contest 386)Raymond Jones · 2:16 · 48 views
  10. LeetCode | 3084. Count Substrings Starting and Ending with Given Character | Weekly Contest 389Coding with Bobby · 3:32 · 42 views

The 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.

Example 1:

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

Output: 6

Explanation: Substrings starting and ending with "a" are: "abada", "abada", "abada", "abada", "abada", "abada".

Example 2:

Input: s = "zzz", c = "z"

Output: 6

Explanation: There are a total of 6 substrings in s and all start and end with "z".

Constraints:

  • 1 <= s.length <= 105
  • s and c consist only of lowercase English letters.

Approach overview

Problem Overview: You are given a string s and a character c. The task is to count how many substrings start and end with c. Any substring is valid as long as its first and last characters match the given character.

The key observation: if the character c appears k times in the string, every occurrence can pair with itself or any later occurrence to form a valid substring. That turns the problem into a simple counting problem rather than generating substrings explicitly.

Approach 1: Two-Pointers and Counting (Time: O(n), Space: O(1))

Traverse the string once and keep a counter of how many times the character c has appeared so far. Every time you encounter c, increment the counter and add its value to the result. This works because each new occurrence can form substrings with all previous occurrences, including itself. Instead of maintaining explicit two pointers, the running count implicitly represents all possible starting points for substrings ending at the current index. This approach relies on simple iteration and arithmetic, making it the most efficient solution for large inputs.

Approach 2: Precomputing Positions of Character (Time: O(n), Space: O(k))

First iterate through the string and store the indices where c appears in a list. If there are k such positions, the number of valid substrings equals k * (k + 1) / 2. Each occurrence can be the start of a substring that ends at itself or any later occurrence. This approach separates the discovery of relevant characters from the counting step, which can make the logic easier to reason about when analyzing substring boundaries.

Both approaches rely on the same mathematical insight: counting combinations of positions rather than constructing substrings. Problems like this frequently appear in string processing and counting patterns, and the formula-based reasoning comes from basic math combinatorics.

Recommended for interviews: The single-pass counting approach is what most interviewers expect. It demonstrates that you recognized the combinatorial pattern and avoided unnecessary substring generation. Showing the mathematical reasoning behind k * (k + 1) / 2 signals strong problem‑solving intuition.

Approach 1: Approach 1: Two-Pointers and Counting

In this approach, we use the two-pointers method to find positions where the substring starts and ends with the character 'c'. We have a simple count of all such occurrences using combinations.

def count_substrings(s, c):
    count = 0
    prev_count = 0
    for char in s:
        if char == c:
            prev_count += 1
            count += prev_count
    return count

s = "abada"
c = 'a'
print(count_substrings(s, c))  # Output: 6
public class SubstringCounter {
    public static int countSubstrings(String s, char c) {
        int count = 0;
        int prevCount = 0;
        for (char ch : s.toCharArray()) {
            if (ch == c) {
                prevCount++;
                count += prevCount;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String s = "abada";
        char c = 'a';
        System.out.println(countSubstrings(s, c));  // Output: 6
    }
}
#include <iostream>
#include <string>
using namespace std;

int countSubstrings(const string &s, char c) {
    int count = 0;
    int prevCount = 0;
    for (char ch : s) {
        if (ch == c) {
            prevCount++;
            count += prevCount;
        }
    }
    return count;
}

int main() {
    string s = "abada";
    char c = 'a';
    cout << countSubstrings(s, c) << endl;  // Output: 6
    return 0;
}
function countSubstrings(s, c) {
    let count = 0;
    let prevCount = 0;
    for (const char of s) {
        if (char === c) {
            prevCount++;
            count += prevCount;
        }
    }
    return count;
}

const s = "abada";
const c = 'a';
console.log(countSubstrings(s, c));  // Output: 6;
#include <stdio.h>
#include <string.h>

int countSubstrings(char* s, char c) {
    int count = 0;
    int prevCount = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == c) {
            prevCount++;
            count += prevCount;
        }
    }
    return count;
}

int main() {
    char s[] = "abada";
    char c = 'a';
    printf("%d\n", countSubstrings(s, c));  // Output: 6
    return 0;
}
using System;

public class SubstringCounter {
    public static int CountSubstrings(string s, char c) {
        int count = 0;
        int prevCount = 0;
        foreach (char ch in s) {
            if (ch == c) {
                prevCount++;
                count += prevCount;
            }
        }
        return count;
    }

    public static void Main() {
        string s = "abada";
        char c = 'a';
        Console.WriteLine(CountSubstrings(s, c));  // Output: 6
    }
}

Each time the character 'c' is found, we increment 'prev_count', which tracks the number of potential substring starts. These are added up to the main 'count' which holds the total number of valid substrings.

Complexity

Time Complexity: O(n), Space Complexity: O(1)

Try this approach in the editor

Approach 2: Approach 2: Precomputing Positions of Character

This approach involves precomputing all positions of the character 'c' and then using combinations of these positions to calculate the number of valid substrings.

def count_substrings(s, c):
    positions = [i for i, char in enumerate(s) if char == c]
    count = 0
    pos_count = len(positions)
    for i in range(pos_count):
        count += pos_count - i
    return count

s = "abada"
c = 'a'
print(count_substrings(s, c))  # Output: 6
import java.util.ArrayList;

public class SubstringCounter {
    public static int countSubstrings(String s, char c) {
        ArrayList<Integer> positions = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                positions.add(i);
            }
        }
        
        int count = 0;
        int posCount = positions.size();
        for (int i = 0; i < posCount; i++) {
            count += posCount - i;
        }
        return count;
    }

    public static void main(String[] args) {
        String s = "abada";
        char c = 'a';
        System.out.println(countSubstrings(s, c));  // Output: 6
    }
}
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int countSubstrings(const string &s, char c) {
    vector<int> positions;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == c) {
            positions.push_back(i);
        }
    }
    
    int count = 0;
    int posCount = positions.size();
    for (int i = 0; i < posCount; i++) {
        count += posCount - i;
    }
    return count;
}

int main() {
    string s = "abada";
    char c = 'a';
    cout << countSubstrings(s, c) << endl;  // Output: 6
    return 0;
}
function countSubstrings(s, c) {
    const positions = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === c) {
            positions.push(i);
        }
    }

    let count = 0;
    const posCount = positions.length;
    for (let i = 0; i < posCount; i++) {
        count += posCount - i;
    }
    return count;
}

const s = "abada";
const c = 'a';
console.log(countSubstrings(s, c));  // Output: 6;
#include <stdio.h>
#include <string.h>

int countSubstrings(char* s, char c) {
    int count = 0;
    int positions[100000];  // This should be enough, as 1 <= |s| <= 10^5
    int posCount = 0;

    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == c) {
            positions[posCount++] = i;
        }
    }

    // Calculate (posCount choose 2) + posCount
    for (int i = 0; i < posCount; i++) {
        count += posCount - i;
    }
    
    return count;
}

int main() {
    char s[] = "abada";
    char c = 'a';
    printf("%d\n", countSubstrings(s, c));  // Output: 6
    return 0;
}
using System;
using System.Collections.Generic;

public class SubstringCounter {
    public static int CountSubstrings(string s, char c) {
        List<int> positions = new List<int>();
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == c) {
                positions.Add(i);
            }
        }
        
        int count = 0;
        int posCount = positions.Count;
        for (int i = 0; i < posCount; i++) {
            count += posCount - i;
        }
        return count;
    }

    public static void Main() {
        string s = "abada";
        char c = 'a';
        Console.WriteLine(CountSubstrings(s, c));  // Output: 6
    }
}

We first determine the indices at which 'c' occurs in the string. With these indices, the number of valid substrings is derived from counting the combinations of the indices as start and endpoints.

Complexity

Time Complexity: O(n), Space Complexity: O(n)

Try this approach in the editor

Approach 3: Mathematics

First, we can count the number of character c in string s, denoted as cnt.

Each character c can form a substring on its own, so there are cnt substrings that meet the condition. Each character c can form a substring with other c characters, so there are \frac{cnt times (cnt - 1)}{2} substrings that meet the condition.

Therefore, the answer is cnt + \frac{cnt times (cnt - 1)}{2}.

The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).

function countSubstrings(s: string, c: string): number {
    const cnt = s.split('').filter(ch => ch === c).length;
    return cnt + Math.floor((cnt * (cnt - 1)) / 2);
}
func countSubstrings(s string, c byte) int64 {
	cnt := int64(strings.Count(s, string(c)))
	return cnt + cnt*(cnt-1)/2
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Approach 1: Two-Pointers and Counting

Time Complexity: O(n), Space Complexity: O(1)

Approach 2: Precomputing Positions of Character

Time Complexity: O(n), Space Complexity: O(n)

Mathematics–

Complexity analysis

ApproachTimeSpaceWhen to Use
Two-Pointers and CountingO(n)O(1)Best general solution. Single pass with constant memory.
Precomputing Positions of CharacterO(n)O(k)Useful when you want explicit indices of the character for further processing.

Frequently asked questions

Is Count Substrings Starting and Ending with Given Character easy or hard?

The problem is typically considered easy to medium difficulty. The implementation is simple once you recognize the counting pattern, but the key challenge is spotting the combinatorial insight that avoids brute-force substring generation.

Count Substrings Starting and Ending with Given Character Python/Java solution

Most implementations follow the same logic across languages. Iterate through the string, increment a counter when the target character appears, and add that counter to the result. This pattern translates directly to Python, Java, C++, JavaScript, and C# with O(n) time complexity.

How to solve Count Substrings Starting and Ending with Given Character in O(n)?

Traverse the string and maintain a variable that counts how many times the target character has appeared. Whenever the current character equals the target, increment the counter and add it to the result. Each occurrence forms substrings with all previous occurrences, giving the correct total in linear time.

What is the best approach for Count Substrings Starting and Ending with Given Character?

The optimal approach is a single-pass counting technique. Iterate through the string and keep a running count of how many times the target character has appeared. Each new occurrence adds that count to the answer. This runs in O(n) time and O(1) space and avoids generating substrings explicitly.

Is Count Substrings Starting and Ending with Given Character asked at Google/Amazon/Meta?

Substring counting and combinatorial string problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often involve counting substrings with specific constraints, using prefix counts, hash maps, or mathematical observations.

What data structure is used in Count Substrings Starting and Ending with Given Character?

The optimal solution does not require complex data structures. It mainly uses a simple counter while iterating through the string. An alternative approach stores the indices of the target character in an array or list and applies a combinatorial formula.

What is the time complexity of Count Substrings Starting and Ending with Given Character?

The optimal solution runs in O(n) time where n is the length of the string. The algorithm scans the string once and performs constant-time operations for each character. Space complexity is O(1) for the counting approach or O(k) if you store indices of the character.

Comments

Now write it yourselfClose this page and solve Count Substrings Starting and Ending with Given Character in the editor, without looking.
Practise Count Substrings Starting and Ending with Given Character