code_library-100-Questions-/findMaxLen.cpp at main · manishsinghkuswaha/code_library-100-Questions- · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/* Approach : 1 Brute Force
 Time Complexity : O(n*n)
 Space Complexity : O(1)
*/

class Solution {
  public:
    int findMaxLen(string s) {
    int count = 0;
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        count = 0;
        for (int j = i; j < s.length(); j++) {
            if (s[j] == '(') {
                count++;
            } else {
                count--;
            }
            if (count < 0) {
                break;

            }
            if (count == 0) {
                if (j - i + 1 > max) {
                    max = j - i + 1;
                }
            }
        }
    }
    return max;
    }
};

/*Approach 2 : Using Stack
               In this approach we initialize stack by pushing -1. -1 acts as a base for the next valid
	       substring and then we store indexes of the opening braces encountered in the stack. As
	       soon as we encounter a closing bracket we pop the index stored at the top and if while
	       popping, the stack is not empty that means there exists a boundary or base index then we can
	       calculate the length by subtracting current index with the stack's top.
 Time Complexity : O(n)
 Space Complexity : O(n)

*/

class Solution {
  public:
    int findMaxLen(string s) {
        stack<int> st;
        int res = 0;
        st.push(-1);
        for(int i = 0; i < s.length(); i++){
            if(s[i] == '(')
                st.push(i);
            else{
                st.pop();
                if(st.empty())
                    st.push(i);
                else
                    res = max(res, i-st.top());
            }
        }
        return res;
    }
};

/* Approach 3 : Without extra space.
   Time Complexity : O(n)
   Space Complexity : O(1)
*/
class Solution {
  public:
    int findMaxLen(string s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(')
                left++;
            else
                right++;

            if (left == right)
                maxlength = max(maxlength, 2 * right);
            else if (right >= left)
                left = right = 0;

        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] == '(')
                left++;
            else
                right++;

            if (left == right)
                maxlength = max(maxlength, 2 * left);
            else if (left >= right)
                left = right = 0;
        }
        return maxlength;
    }
};