Substrings of Size Three with Distinct Characters — LeetCode 1876 Python Solution
EasyHash TableStringCountingSliding Window
- Problem
- #1876
- Pattern
- Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The problem
A string is good if there are no repeated characters. Given a string s, return the number of good substrings of length three in s.
Example
- Input
- s = "xyzzaz"
- Output
- 1
- Explanation
- There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz".
Python solution
Python
class Solution:
def countGoodSubstrings(self, s: str) -> int:
ans = mask = l = 0
for r, x in enumerate(map(lambda c: ord(c) - 97, s)):
while mask >> x & 1:
y = ord(s[l]) - 97
mask ^= 1 << y
l += 1
mask |= 1 << x
ans += int(r - l + 1 >= 3)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n), where n is the length of the string s |
| Space | O(1) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1876. Substrings of Size Three with Distinct Characters is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
LeetCode 2981Find Longest Special Substring That Occurs Thrice IMediumLeetCode 2982Find Longest Special Substring That Occurs Thrice IIMediumLeetCode 3Longest Substring Without Repeating CharactersMediumLeetCode 30Substring with Concatenation of All WordsHardLeetCode 76Minimum Window SubstringHardLeetCode 187Repeated DNA SequencesMedium
Frequently asked questions
- How hard is LeetCode 1876. Substrings of Size Three with Distinct Characters?
- LeetCode 1876. Substrings of Size Three with Distinct Characters is rated Easy on LeetCode.
- What is the time complexity of LeetCode 1876. Substrings of Size Three with Distinct Characters?
- The Python solution on this page runs in O(n), where n is the length of the string s.
- What is the space complexity of LeetCode 1876. Substrings of Size Three with Distinct Characters?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1876. Substrings of Size Three with Distinct Characters cover?
- LeetCode 1876. Substrings of Size Three with Distinct Characters is tagged Hash Table, String, Counting and Sliding Window on LeetCode.