Count Substrings Starting and Ending with Given Character

MEDIUM

Description

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

Approaches

Checkout 2 different approaches to solve Count Substrings Starting and Ending with Given Character. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Count Substrings Starting and Ending with Given Character. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Count Substrings Starting and Ending with Given Character

Patterns:

MathCounting

Data Structures:

String