1180. Count Substrings with Only One Distinct Letter
Model: qwen2.5-coder:14b
Topics: Math,String
FAANG asked: 0
Acceptance rate: 77.9%
Problem Breakdown
The problem requires counting all substrings in a given string S where each substring contains only one distinct letter. The input is a single string consisting of lowercase English letters, and the output is an integer representing the count of such substrings.
Inputs:
- A string
S(1 <= S.length <= 1000)
Outputs:
- An integer representing the number of substrings with only one distinct letter
Implicit Constraints/Edge Cases:
- The string can be as short as 1 character or as long as 1000 characters.
- The string consists only of lowercase English letters.
Intuition
A brute-force approach would involve generating all possible substrings and checking if each substring contains only one distinct letter. This approach is inefficient with a time complexity of O(n^3) due to the generation and checking of substrings, which is not suitable given the constraints.
The key insight is to recognize that for any contiguous segment of identical characters in the string, we can calculate the number of substrings directly using the formula for the sum of the first k natural numbers: ( \frac{k(k+1)}{2} ), where k is the length of the segment. This reduces the time complexity to O(n).
Approach
- Initialize a counter
total_countto keep track of the total number of substrings with only one distinct letter. - Use two pointers,
startandend, both initially set to 0. Thestartpointer marks the beginning of a segment of identical characters, and theendpointer traverses the string. - Iterate through the string with the
endpointer:- If the character at
endis the same as the character atstart, incrementend. - If they are different, calculate the length of the current segment (
k = end - start). Use the formula ( \frac{k(k+1)}{2} ) to add the number of substrings in this segment tototal_count. Then, movestarttoendand continue.
- If the character at
- After the loop, handle the last segment by calculating its contribution using the same formula.
- Return
total_count.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We traverse the string once with two pointers.
- Space Complexity: O(1). We use a constant amount of extra space for variables.
Solution
def countLetters(S: str) -> int:
total_count = 0
start = 0
for end in range(len(S)):
if S[end] != S[start]:
k = end - start
total_count += k * (k + 1) // 2
start = end
# Handle the last segment
k = len(S) - start
total_count += k * (k + 1) // 2
return total_count
Edge Cases Handled
- Single Character String: If the string has only one character, the formula ( \frac{k(k+1)}{2} ) with
k = 1correctly returns 1. - All Characters Identical: For a string like “aaaaaaaaaa”, the entire string is one segment, and the formula calculates the total number of substrings as expected.
- Mixed Segments: The approach naturally handles strings with mixed segments of identical characters by resetting
startwhenever a new character is encountered.