D
DevExCode

LeetCode 1358: Number of Substrings Containing All Three Characters Solution

Master LeetCode problem 1358 (Number of Substrings Containing All Three Characters), 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.

1358. Number of Substrings Containing All Three Characters

Medium
Hash TableStringSliding Window

Problem Explanation

Explanation:

To solve this problem, we can use a sliding window approach. We will iterate over the given string and maintain a window that contains at least one occurrence of all characters a, b, and c. We will keep expanding the window until we have all three characters present, then count the number of substrings that can be formed within that window.

Algorithm:

  1. Initialize three pointers left, right, and count to 0.
  2. Iterate over the string using the right pointer:
    • Increment the count of the character at right pointer.
    • If the count of the character at right pointer is 1, increment a uniqueChars counter.
    • While uniqueChars is greater than 3, decrement the count of the character at left pointer and move left pointer to the right.
    • Calculate the number of substrings that can be formed within the window (right - left + 1) and add it to the result.
  3. Return the total count of substrings.

Time Complexity:

The time complexity of this solution is O(N), where N is the length of the input string s.

Space Complexity:

The space complexity of this solution is O(1).

:

Solution Code

class Solution {
    public int numberOfSubstrings(String s) {
        int[] count = new int[3];
        int left = 0, uniqueChars = 0, result = 0;

        for (int right = 0; right < s.length(); right++) {
            count[s.charAt(right) - 'a']++;
            if (count[s.charAt(right) - 'a'] == 1) {
                uniqueChars++;
            }

            while (uniqueChars > 3) {
                count[s.charAt(left) - 'a']--;
                if (count[s.charAt(left) - 'a'] == 0) {
                    uniqueChars--;
                }
                left++;
            }

            result += (right - left + 1);
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1358 (Number of Substrings Containing All Three Characters)?

This page provides optimized solutions for LeetCode problem 1358 (Number of Substrings Containing All Three Characters) 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 1358 (Number of Substrings Containing All Three Characters)?

The time complexity for LeetCode 1358 (Number of Substrings Containing All Three Characters) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1358 on DevExCode?

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

Back to LeetCode Solutions