Scale Engineer

Count Substrings Starting and Ending with Given Character

Med
#2740Time: 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.
Patterns
MathCounting
Data structures
String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem