D
DevExCode

LeetCode 2743: Count Substrings Without Repeating Character Solution

Master LeetCode problem 2743 (Count Substrings Without Repeating Character), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2743. Count Substrings Without Repeating Character

Medium
Hash TableStringSliding Window

Problem Explanation

Explanation

To solve this problem, we can use a sliding window approach to iterate through the given string. We will keep track of the characters we have seen so far in a set. Whenever we encounter a repeating character while expanding the window, we will shrink the window from the left until the repeating character is no longer in the window.

At each step, we will count the number of substrings that can be formed considering the current window, and add it to the total count. The total count will be the answer to the problem.

Algorithm:

  1. Initialize variables: start = 0, end = 0, count = 0, seen set to store seen characters.
  2. Iterate end over the string:
    • If the current character at end is not in seen, add it to seen.
    • If the current character at end is in seen, increment start until the current character is no longer in seen.
    • Add the number of substrings that can be formed with the current window size to count.
  3. Return the final count.

Time Complexity: O(n) where n is the length of the input string. Space Complexity: O(min(n, 26)) as the maximum size of the set seen can be at most 26 (all lowercase letters).

Solution Code

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        Set<Character> seen = new HashSet<>();
        int start = 0;

        for (int end = 0; end < n; end++) {
            char c = s.charAt(end);
            while (seen.contains(c)) {
                seen.remove(s.charAt(start));
                start++;
            }
            seen.add(c);
            count += (end - start + 1);
        }

        return count;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 2743 (Count Substrings Without Repeating Character)?

This page provides optimized solutions for LeetCode problem 2743 (Count Substrings Without Repeating Character) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2743 (Count Substrings Without Repeating Character)?

The time complexity for LeetCode 2743 (Count Substrings Without Repeating Character) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2743 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2743 in Java, C++, or Python.

Back to LeetCode Solutions