# Count Substrings Starting and Ending with Given Character
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-substrings-starting-and-ending-with-given-character)
Canonical: https://scaleengineer.com/dsa/problems/count-substrings-starting-and-ending-with-given-character
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** String
---
## 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: `"**a**bada"`, `"**aba**da"`, `"**abada**"`, `"ab**a**da"`, `"ab**ada**"`, `"abad**a**"`.

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

# Approaches
## Brute-Force with Nested Loops
This approach involves iterating through all possible substrings of the given string `s`. For each substring, we check if it starts and ends with the specified character `c`. If it does, we increment a counter.
**Time:** O(N^2), where N is the length of the string `s`. The two nested loops cause the algorithm to check every possible pair of start and end indices, leading to a quadratic runtime. · **Space:** O(1), as we only use a few variables to store the count and loop indices, which does not depend on the input string's size.
**Pros:** Simple to understand and implement.; It directly translates the problem definition into code.
**Cons:** Highly inefficient due to its quadratic time complexity.; For the given constraints (s.length up to 10^5), this approach will be too slow and result in a 'Time Limit Exceeded' (TLE) error on most platforms.
### Explanation
The algorithm uses two nested loops to define the start and end points of every substring. The outer loop, with index `i`, iterates from the beginning to the end of the string, marking the potential start of a substring. The inner loop, with index `j`, iterates from `i` to the end of the string, marking the potential end of a substring. A substring is valid if the characters at both the start index `i` and the end index `j` are equal to the target character `c`. We maintain a counter that is incremented for every such valid pair of indices `(i, j)`.

```java
class Solution {
    public long countSubstrings(String s, char c) {
        long count = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == c && s.charAt(j) == c) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter variable `count` to 0.
- Use a nested loop structure. The outer loop with index `i` iterates from `0` to `n-1` (where `n` is the string length) to select a starting character.
- The inner loop with index `j` iterates from `i` to `n-1` to select an ending character.
- Inside the loops, check if `s.charAt(i)` is equal to the target character `c` AND `s.charAt(j)` is also equal to `c`.
- If both conditions are true, it means we have found a valid substring. Increment the `count`.
- After both loops have finished, return the total `count`.

## Optimal Approach using Combinatorial Counting
A much more efficient approach is to reframe the problem from a combinatorial perspective. A substring that starts and ends with `c` is formed by choosing two occurrences of `c` in the string, one for the start and one for the end (the start and end can be the same occurrence). If the character `c` appears `k` times, the problem reduces to finding the number of ways to choose two positions from these `k` occurrences, where the order doesn't matter and repetition is allowed.
**Time:** O(N), where N is the length of the string `s`. We only need to perform a single pass over the string to count the occurrences of `c`. The final calculation is a constant time operation. · **Space:** O(1), as we only need a single variable to store the count of `c`, regardless of the input string's length.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Optimal solution for this problem.; Simple to implement once the combinatorial logic is understood.
**Cons:** The underlying mathematical insight might not be immediately obvious to everyone.
### Explanation
The core idea is that any substring starting and ending with `c` is uniquely defined by the indices of its starting and ending `c`. Let's say the character `c` appears `k` times in the string. The first occurrence of `c` can form a valid substring with itself and the `k-1` other occurrences of `c` that appear after it, resulting in `k` substrings. The second occurrence of `c` can form a valid substring with itself and the `k-2` occurrences after it, giving `k-1` substrings. This pattern continues until the last occurrence of `c`, which can only form a substring with itself (1 substring). The total count is the sum `k + (k-1) + ... + 1`. This is the sum of the first `k` positive integers, which has a well-known formula: `k * (k + 1) / 2`. The algorithm is thus to first count occurrences of `c` and then apply this formula. Note that the result can be large, so a 64-bit integer type (`long`) should be used for the count and the final result to prevent overflow.

```java
class Solution {
    public long countSubstrings(String s, char c) {
        long countOfC = 0;
        for (char ch : s.toCharArray()) {
            if (ch == c) {
                countOfC++;
            }
        }
        // The number of substrings is the sum of 1 + 2 + ... + countOfC
        // which is the formula for the k-th triangular number: k * (k + 1) / 2
        return countOfC * (countOfC + 1) / 2;
    }
}
```
### Algorithm
- Initialize a counter `k` to 0. It's important to use a 64-bit integer type (like `long` in Java) for this counter to avoid potential overflow.
- Iterate through the input string `s` just once, from the first character to the last.
- In each iteration, check if the current character is equal to the target character `c`.
- If it is, increment the counter `k`.
- After the loop finishes, `k` will hold the total number of occurrences of `c` in the string.
- The total number of valid substrings is the sum of integers from 1 to `k`. This can be calculated directly using the formula for the sum of an arithmetic series: `(k * (k + 1)) / 2`.
- Return this calculated value.

# Solutions
### Java

```java
class Solution {
public
  long countSubstrings(String s, char c) {
    long cnt = s.chars().filter(ch->ch == c).count();
    return cnt + cnt * (cnt - 1) / 2;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long countSubstrings(string s, char c) {
    long long cnt = ranges ::count(s, c);
    return cnt + cnt * (cnt - 1) / 2;
  }
};

```

### Python

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

```