We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Substrings Without Repeating Character

Number: 2890

Difficulty: Medium

Paid? Yes

Companies: Yandex

Problem Description

Given a string s consisting only of lowercase English letters, we need to count the number of special substrings. A substring is considered special if it does not contain any repeating characters. For example, in "pop", the substring "po" is special whereas "pop" is not because 'p' appears twice.

Key Insights

  • We are asked to count all substrings that do not have a repeated character.
  • A valid special substring is defined by a contiguous segment with all unique characters.
  • We can use the sliding window technique to efficiently enumerate substrings that satisfy the constraints.
  • For each position in the string (as the end of the window), the number of valid substrings ending at that position equals the length of the current window (i.e., the number of choices for the starting position).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string since each character is processed at most twice. Space Complexity: O(1) in practice, as the structure used to track characters will have at most 26 keys (the number of lowercase letters).

Solution

We use the sliding window technique with two pointers (left and right). The idea is to maintain a window that always contains unique characters. As we move the right pointer to explore new characters, if a duplicate is encountered, we move the left pointer until the duplicate is removed from the current window. At every step, the size of the valid window gives the count of new special substrings ending at the current index. By summing these counts up for every index, we obtain the total number of special substrings.

Code Solutions

# Python solution using the sliding window technique

def countSpecialSubstrings(s: str) -> int:
    n = len(s)
    left = 0  # Left pointer for the sliding window
    seen = set()  # Set to store unique characters in the current window
    result = 0  # To store the total count of special substrings

    # Iterate over the string with right pointer
    for right in range(n):
        # If the character already exists in the current window,
        # move the left pointer until it's removed
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        # Add the current character to the set
        seen.add(s[right])
        # The number of valid substrings ending at 'right' is the window size (right - left + 1)
        result += (right - left + 1)
    
    return result

# Example usage:
s1 = "abcd"
print(countSpecialSubstrings(s1))  # Output: 10
← Back to All Questions