leetcode

commit ef75c4a89367a5bad7e5e7301cd437489cf02cda
parent 46c20c853638151a87a1dfe92f55f8227dc2dc7c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun,  7 Apr 2024 17:37:36 +0200

Daily Problem

Diffstat:
A
Problems/0678.cpp
 | 
17
+++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 18 insertions(+), 0 deletions(-)
diff --git a/Problems/0678.cpp b/Problems/0678.cpp
@@ -0,0 +1,17 @@
+class Solution {
+  public:
+    bool checkValidString(const string &s) const {
+        int mini = 0, maxi = 0;
+        for (const char c : s) {
+            if (c == '(')
+                mini++, maxi++;
+            else if (c == ')')
+                mini--, maxi--;
+            else if (c == '*')
+                maxi++, mini--;
+            if (maxi < 0) return false;
+            mini = max(mini, 0);
+        }
+        return mini == 0;
+    }
+};
diff --git a/README.md b/README.md
@@ -440,6 +440,7 @@ for solving problems.
 |  0673  |   Medium   | [Number of Longest Increasing Subsequence](Problems/0673.cpp)                                      |
 |  0676  |   Medium   | [Implement Magic Dictionary](Problems/0676.cpp)                                                    |
 |  0677  |   Medium   | [Map Sum Pairs](Problems/0677.cpp)                                                                 |
+|  0678  |   Medium   | [Valid Parenthesis String](Problems/0678.cpp)                                                      |
 |  0684  |   Medium   | [Redundant Connection](Problems/0684.cpp)                                                          |
 |  0688  |   Medium   | [Knight Probability in Chessboard](Problems/0688.cpp)                                              |
 |  0690  |   Medium   | [Employee Importance](Problems/0690.cpp)                                                           |