What is the time complexity of Number of Substrings Containing All Three Characters?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Number of Substrings Containing All Three Characters?

This problem uses Hash Table, String, Sliding Window. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Number of Substrings Containing All Three Characters?

Insight 1: The problem can be efficiently solved using the sliding window technique. Insight 2: We only need to keep track of the counts of each character ('a', 'b', 'c') within the current window.

Which companies ask LeetCode 1358. Number of Substrings Containing All Three Characters in interviews?

This problem is frequently asked at DE Shaw, PayPal.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Number of Substrings Containing All Three Characters - LeetCode 1358 Solution

Number of Substrings Containing All Three Characters - Complete Solution Guide

Number of Substrings Containing All Three Characters is LeetCode problem 1358, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given a string s consisting only of characters a , b and c . Return the number of substrings containing at least one occurrence of all these characters a , b and c . Example 1: Input: s = "abcabc" Output: 10 Explanation: The substrings containing at least one occurrence of the characters a , b and c are " abc ", " abca ", " abcab ", " abcabc ", " bca ", " bcab ", " bcabc ", " cab ", " cabc " and " abc " ( again ) . Example 2: Input: s = "aaacb" Output: 3 Explanation: The substrings containing at

Detailed Explanation

The problem requires us to find the number of substrings in a given string `s` (consisting only of 'a', 'b', and 'c' characters) that contain at least one occurrence of each character ('a', 'b', and 'c'). The input is the string `s`, and the output is the count of such substrings. The string length is between 3 and 50,000.

Solution Approach

The solution uses a sliding window approach. We maintain a window defined by `left` and `right` pointers. We expand the window by moving the `right` pointer one step at a time, updating the counts of each character in the window. When the window contains at least one of each character 'a', 'b', and 'c', we shrink the window from the left by incrementing the `left` pointer. The number of valid substrings ending at the current `right` position is equal to the current `left` index. We add this value to the total count of valid substrings.

Step-by-Step Algorithm

Step 1: Initialize a hash map (or array) to store the counts of characters 'a', 'b', and 'c'.
Step 2: Initialize `left` pointer to 0 and `res` (result counter) to 0.
Step 3: Iterate through the string using the `right` pointer.
Step 4: Increment the count of the character at the `right` pointer in the hash map.
Step 5: While the window contains at least one 'a', one 'b', and one 'c', decrement the count of the character at the `left` pointer and increment `left` pointer.
Step 6: After shrinking the window as much as possible, increment `res` by `left`. This represents the number of valid substrings ending at the current `right` position.
Step 7: Repeat steps 3-6 until the `right` pointer reaches the end of the string.
Step 8: Return `res`.

Key Insights

Insight 1: The problem can be efficiently solved using the sliding window technique.
Insight 2: We only need to keep track of the counts of each character ('a', 'b', 'c') within the current window.
Insight 3: For each valid window (containing all three characters), any substring ending at the right boundary starting from the beginning of the string up to current left pointer position will contain all three characters

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Hash Table, String, Sliding Window.

Companies

Asked at: DE Shaw, PayPal.

Number of Substrings Containing All Three Characters | LeetCode 1358

Medium

Hash Table String Sliding Window

Time: O(n)Space: O(1)

Solution Code

Available in:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numberOfSubstrings(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        counts.put('a', 0);
        counts.put('b', 0);
        counts.put('c', 0);
        
        int res = 0;
        int left = 0;
        int n = s.length();
        
        for (int right = 0; right < n; right++) {
            counts.put(s.charAt(right), counts.get(s.charAt(right)) + 1);
            
            while (counts.get('a') > 0 && counts.get('b') > 0 && counts.get('c') > 0) {
                counts.put(s.charAt(left), counts.get(s.charAt(left)) - 1);
                left++;
            }
            
            res += left;
        }
        
        return res;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1358: Number of Substrings Containing All Three Characters - Detailed explanation and solution approaches.

Topics

Hash Table String Sliding Window

Companies

DE ShawPayPal

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:1358

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Initialize a hash map (or array) to store the counts of characters 'a', 'b', and 'c'.
2
Step 2: Initialize `left` pointer to 0 and `res` (result counter) to 0.
3
Step 3: Iterate through the string using the `right` pointer.
4
Step 4: Increment the count of the character at the `right` pointer in the hash map.
5
Step 5: While the window contains at least one 'a', one 'b', and one 'c', decrement the count of the character at the `left` pointer and increment `left` pointer.
6
Step 6: After shrinking the window as much as possible, increment `res` by `left`. This represents the number of valid substrings ending at the current `right` position.
7
Step 7: Repeat steps 3-6 until the `right` pointer reaches the end of the string.
8
Step 8: Return `res`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(n) because we iterate through the string at most twice (once for the right pointer and once in the worst case for the left pointer). The space complexity is O(1) because the space used is independent of the input size. The character counts array (or hash map) has fixed size of 3 irrespective of the length of the string.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible substrings and check if each substring contains all three characters ('a', 'b', and 'c').

Time: O(n^3), where n is the length of the string `s`. Generating all substrings takes O(n^2) and checking each substring for all three chars takes O(n) in the worst case, making a total of O(n^3)Space: O(n), due to substring creation

Trade-offs: This approach is very inefficient and would likely result in a Time Limit Exceeded (TLE) error on LeetCode for larger input strings. It is only suitable for very small input sizes. Sliding window approach provides significant performance improvement.

✨

Key Insights

1Insight 1: The problem can be efficiently solved using the sliding window technique.
2Insight 2: We only need to keep track of the counts of each character ('a', 'b', 'c') within the current window.
3Insight 3: For each valid window (containing all three characters), any substring ending at the right boundary starting from the beginning of the string up to current left pointer position will contain all three characters

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Sliding Window

A moving "window" over data to process subsets efficiently.

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty string (not possible based on constraints, but handling it generally is good practice). The code would return 0 as the loop won't execute.
Edge case 2: String with only one or two distinct characters. The while loop condition `counts['a'] > 0 and counts['b'] > 0 and counts['c'] > 0` prevents any window that don't have all three chars from being considered.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly updating counts of characters. Forgetting to decrement the counts when shrinking the window.

✗Common mistake 2: Not understanding how to correctly update result. `res += left` is not intuitive. The correct intuition is to understand, when a window is valid, then substring ends at current right position starting all way from index 0 to left pointer, are also valid. Which accounts to the substring of length equals the left pointer.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Text analysis. This algorithm can be used to find the number of text segments (substrings) in a document that contain a specific set of keywords.

🏦Real-world scenario 2: Bioinformatics. Analyzing DNA sequences to find segments that contain a required set of genes.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 7, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

❓

Frequently Asked Questions

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I handle string manipulation efficiently?

In languages with immutable strings (Java, Python, C#), use StringBuilder/list to avoid O(n) concatenation cost. Consider using character arrays for in-place modifications. For pattern matching, consider KMP or Rabin-Karp for O(n+m) complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Number of Substrings Containing All Three Characters"?

For this medium-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?