Problem

You are given a string s and a character c. Return _the total number of substrings of _s that start and end withc .

Examples

Example 1

1
2
3
4
5
6
7
8


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

Output: 6

Explanation: Substrings starting and ending with `"a"` are: `"**_a_**
bada"`, `"_**aba**_ da"`, `"_**abada**_ "`, `"ab _**a**_ da"`, `"ab _**ada**_
"`, `"abad _**a**_ "`.

Example 2

1
2
3
4
5
6
7


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 <= 10^5
  • s and c consist only of lowercase English letters.

Solution

Method 1 – Counting Occurrences

Intuition

Every substring that starts and ends with the given character c can be uniquely identified by picking two indices where c occurs (possibly the same index). The number of such substrings is the number of ways to choose a start and end position among all positions where c appears, including single-character substrings.

Approach

  1. Count the number of times c appears in the string s (let’s call it cnt).
  2. The number of substrings that start and end with c is cnt * (cnt + 1) // 2.
    • This is because for each pair of positions (i, j) with i <= j and s[i] == s[j] == c, the substring s[i:j+1] starts and ends with c.
  3. Return this value.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    long long countSubstrings(string s, char c) {
        long long cnt = 0;
        for (char ch : s) if (ch == c) cnt++;
        return cnt * (cnt + 1) / 2;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

type Solution struct{}
func (Solution) CountSubstrings(s string, c byte) int64 {
    var cnt int64
    for i := 0; i < len(s); i++ {
        if s[i] == c {
            cnt++
        }
    }
    return cnt * (cnt + 1) / 2
}
1
2
3
4
5
6
7

class Solution {
    public long countSubstrings(String s, char c) {
        long cnt = 0;
        for (char ch : s.toCharArray()) if (ch == c) cnt++;
        return cnt * (cnt + 1) / 2;
    }
}
1
2
3
4
5
6

class Solution {
    fun countSubstrings(s: String, c: Char): Long {
        val cnt = s.count { it == c }.toLong()
        return cnt * (cnt + 1) / 2
    }
}
1
2
3
4

class Solution:
    def countSubstrings(self, s: str, c: str) -> int:
        cnt = s.count(c)
        return cnt * (cnt + 1) // 2
1
2
3
4
5
6

impl Solution {
    pub fn count_substrings(s: String, c: char) -> i64 {
        let cnt = s.chars().filter(|&ch| ch == c).count() as i64;
        cnt * (cnt + 1) / 2
    }
}
1
2
3
4
5
6

class Solution {
    countSubstrings(s: string, c: string): number {
        const cnt = s.split('').filter(x => x === c).length;
        return (cnt * (cnt + 1)) / 2;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, since we scan the string once.
  • 🧺 Space complexity: O(1), only a counter is used.