What is the time complexity of Valid Parenthesis String?

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

What data structures are used to solve Valid Parenthesis String?

This problem uses String, Dynamic Programming, Stack, Greedy. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Valid Parenthesis String?

Insight 1: The '*' character introduces flexibility, allowing it to be either '(' or ')' or '' Insight 2: Instead of trying all possible combinations of '*' (which would be exponential), we can keep track of the range of open parentheses possible at each point in the string.

Which companies ask LeetCode 678. Valid Parenthesis String in interviews?

This problem is frequently asked at Alibaba, Blizzard, Roku, ServiceNow, Tekion.

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

Valid Parenthesis String - LeetCode 678 Solution

Valid Parenthesis String - Complete Solution Guide

Valid Parenthesis String is LeetCode problem 678, 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 containing only three types of characters: '(' , ')' and '*' , return true if s is valid . The following rules define a valid string: Any left parenthesis '(' must have a corresponding right parenthesis ')' . Any right parenthesis ')' must have a corresponding left parenthesis '(' . Left parenthesis '(' must go before the corresponding right parenthesis ')' . '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "" . Example 1

Detailed Explanation

The problem asks us to determine if a string `s` containing only '(', ')', and '*' characters is a valid parenthesis string. A valid string must adhere to the following rules: Each '(' must have a corresponding ')', each ')' must have a corresponding '(', the '(' must appear before the corresponding ')', and a '*' can be treated as a single '(', a single ')', or an empty string. The input is a string `s`, and the output is a boolean: `true` if the string is valid, and `false` otherwise. The string's length will be between 1 and 100 characters.

Solution Approach

The solution utilizes a greedy approach by maintaining two counters: `min_open` and `max_open`. `min_open` represents the minimum possible number of unmatched open parentheses, while `max_open` represents the maximum possible number of unmatched open parentheses. The algorithm iterates through the string. When a '(' is encountered, both `min_open` and `max_open` are incremented. When a ')' is encountered, both are decremented. When a '*' is encountered, `min_open` is decremented (treating '*' as ')') and `max_open` is incremented (treating '*' as '('). If `max_open` becomes negative at any point, it indicates that there are more closing parentheses than can be matched, even with the '*' characters acting as open parentheses. In such cases, the string is invalid. After each step, `min_open` is set to `max(0, min_open)` to ensure it doesn't become negative (a negative value would mean we have more closing than opening parenthesis, which is impossible). Finally, the string is valid only if `min_open` is 0 at the end, indicating that all open parentheses have been matched.

Step-by-Step Algorithm

Step 1: Initialize `min_open` and `max_open` to 0.
Step 2: Iterate through the input string `s` character by character.
Step 3: If the current character is '(', increment both `min_open` and `max_open`.
Step 4: If the current character is ')', decrement both `min_open` and `max_open`.
Step 5: If the current character is '*', decrement `min_open` and increment `max_open`.
Step 6: If `max_open` becomes negative, return `false` because there are more closing parentheses than possible opening parentheses.
Step 7: Update `min_open` to `max(0, min_open)` to handle cases where '*' or ')' reduce the open count below zero. In such cases, we can assume that these ')' or '*' are compensating for an already matched string.
Step 8: After iterating through the entire string, return `true` if `min_open` is 0, indicating that all open parentheses have been matched. Otherwise, return `false`.

Key Insights

Insight 1: The '*' character introduces flexibility, allowing it to be either '(' or ')' or ''
Insight 2: Instead of trying all possible combinations of '*' (which would be exponential), we can keep track of the range of open parentheses possible at each point in the string.
Insight 3: Maintain two variables: `min_open` and `max_open`. `min_open` tracks the minimum number of open parentheses needed, and `max_open` tracks the maximum number of open parentheses possible. If `max_open` ever becomes negative, it means there are too many closing parentheses, and the string is invalid. If `min_open` is positive at the end, it means there are too many open parentheses, and the string is invalid. 'min_open' should also be kept non-negative as negative 'min_open' has no valid interpretation.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: String, Dynamic Programming, Stack, Greedy.

Companies

Asked at: Alibaba, Blizzard, Roku, ServiceNow, Tekion.

Valid Parenthesis String | LeetCode 678

Medium

String Dynamic Programming Stack Greedy

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

Solution Code

Available in:

class Solution {
    public boolean checkValidString(String s) {
        int min_open = 0;
        int max_open = 0;

        for (char charr : s.toCharArray()) {
            if (charr == '(') {
                min_open += 1;
                max_open += 1;
            } else if (charr == ')') {
                min_open -= 1;
                max_open -= 1;
            } else {  // char == '*'
                min_open -= 1;
                max_open += 1;
            }

            if (max_open < 0) {
                return false;
            }

            min_open = Math.max(0, min_open);
        }

        return min_open == 0;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 678: Valid Parenthesis String - Detailed explanation and solution approaches.

Topics

String Dynamic Programming Stack Greedy

Companies

AlibabaBlizzardRokuServiceNowTekion

Stats

Difficulty:Medium

Languages:4

Companies:5

Problem #:678

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 `min_open` and `max_open` to 0.
2
Step 2: Iterate through the input string `s` character by character.
3
Step 3: If the current character is '(', increment both `min_open` and `max_open`.
4
Step 4: If the current character is ')', decrement both `min_open` and `max_open`.
5
Step 5: If the current character is '*', decrement `min_open` and increment `max_open`.
6
Step 6: If `max_open` becomes negative, return `false` because there are more closing parentheses than possible opening parentheses.
7
Step 7: Update `min_open` to `max(0, min_open)` to handle cases where '*' or ')' reduce the open count below zero. In such cases, we can assume that these ')' or '*' are compensating for an already matched string.
8
Step 8: After iterating through the entire string, return `true` if `min_open` is 0, indicating that all open parentheses have been matched. Otherwise, return `false`.

💡

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 determined by the single loop that iterates through the string. The space complexity is constant because only two integer variables are used for storing the min and max open counts.

📖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

Stack-based approach

Use two stacks: one for open parentheses '(' and another for star characters '*'. When you encounter a closing parenthesis ')', try to pop an open parenthesis from the open parentheses stack. If that's empty, try to pop a star from the star stack and use it as an open parenthesis. If both stacks are empty, the string is invalid. After processing the string, try to match the remaining open parentheses with star characters. If the index of star is less than open parenthesis index in the original string, it's invalid. This approach is conceptually similar to the two counters method.

Time: O(n)Space: O(n) in the worst case, where the string contains only '(' and '*' characters, resulting in n/2 elements being stored in each stack.

Trade-offs: The stack-based approach is more intuitive for some but uses more space. The two-counter method is more space-efficient but might be less obvious to understand initially.

Dynamic Programming

A DP approach can be used, where dp[i][j] represents whether the substring s[i:j+1] is valid. However, this approach is more complex to implement and understand compared to the greedy approach and does not offer any significant performance benefits in this case.

Time: O(n^3)Space: O(n^2)

Trade-offs: Dynamic programming provides a systematic way to explore all possible combinations, but it leads to a higher time and space complexity compared to the greedy approach. Not recommended due to performance.

✨

Key Insights

1Insight 1: The '*' character introduces flexibility, allowing it to be either '(' or ')' or ''
2Insight 2: Instead of trying all possible combinations of '*' (which would be exponential), we can keep track of the range of open parentheses possible at each point in the string.
3Insight 3: Maintain two variables: `min_open` and `max_open`. `min_open` tracks the minimum number of open parentheses needed, and `max_open` tracks the maximum number of open parentheses possible. If `max_open` ever becomes negative, it means there are too many closing parentheses, and the string is invalid. If `min_open` is positive at the end, it means there are too many open parentheses, and the string is invalid. 'min_open' should also be kept non-negative as negative 'min_open' has no valid interpretation.

📚

Key Terms Explained

For Students

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Greedy Algorithm

Making the best choice at each step without looking ahead.

String

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

Edge Cases

Edge case 1: Empty string. The algorithm will correctly return true because min_open and max_open will be 0.
Edge case 2: String with only '*' characters. The algorithm will correctly return true because `min_open` will be reduced to 0 at the end, and `max_open` will remain non-negative.
Edge case 3: String with imbalanced parentheses, such as '((('. The algorithm will correctly return false because min_open will be greater than zero at the end.
Edge case 4: String with impossible closing parentheses, such as ')('. The algorithm will correctly return false because max_open becomes negative.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Trying to generate all possible combinations of '*' characters. This quickly leads to exponential time complexity and becomes infeasible.

✗Common mistake 2: Only tracking a single count of open parentheses and failing to account for the flexibility provided by the '*' character. This can lead to incorrect results when the string contains a mix of '(', ')', and '*' characters.

✗Common mistake 3: Not resetting the min_open value to max(0, min_open) in each iteration. If min_open becomes negative, we have to assume that these are already matched characters and reset it to zero. Otherwise, the final result might become incorrect.

✗Common mistake 4: Failing to handle the case where open parenthesis exist at the end of the string. The min_open must be 0 at the end for the string to be considered valid.

✅

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: Syntax validation in programming languages. The algorithm can be adapted to check the validity of expressions with different types of delimiters or special characters.

🏦Real-world scenario 2: Data validation. The algorithm can be used to ensure that data structures or strings conform to certain predefined patterns or constraints, where a wildcard character represents a flexible or optional element.

💡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

String problems often involve sliding windows or two pointers. Consider if the character set is limited (lowercase letters = only 26 possibilities).

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Mutating strings directly in languages where strings are immutable. Use StringBuilder or arrays.

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: October 17, 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 13

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

@TechLeadJul 6

❓

Frequently Asked Questions

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.

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

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 "Valid Parenthesis String"?

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

🤖 Need help with this problem?