PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Balanced Parentheses Checking Algorithm using Stack (स्टैक द्वारा कोष्ठकों का संतुलन (Parentheses Matching) जांचना) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Balanced Parentheses Checking uses a Stack to match nested delimiters '()', '{}', and '[]' in O(n) time by enforcing LIFO pairing—where the most recently opened bracket must close first. It catches premature closing underflow, bracket-type mismatches, and leftover unclosed openers at the end.
अध्याय सार: संतुलित कोष्ठक जांच (Balanced Parentheses Checking) स्टैक के LIFO गुण से '()', '{}' और '[]' की सही नेस्टिंग O(n) समय में सत्यापित करती है, जहाँ सबसे अंत में खुला कोष्ठक सबसे पहले बंद होना चाहिए। यह अतिरिक्त बंद कोष्ठक, गलत जोड़ी (जैसे '(]') और अंत में खुले छूटे कोष्ठक—तीनों त्रुटियां पकड़ती है।
Balanced Parentheses Checking Algorithm using Stack: Detailed Notes & Architecture (स्टैक द्वारा कोष्ठकों का संतुलन (Parentheses Matching) जांचना)
1. Why LIFO Nesting Requires a Stack (नेस्टेड कोष्ठकों के लिए स्टैक (LIFO) की अनिवार्यता)
[EN] In valid programming syntax and math formulas, delimiters nest cleanly inside one another: the MOST RECENTLY opened unclosed bracket MUST match the NEXT closing bracket encountered. For example, '{[()]}' is balanced because '(' closes before '[' and '[', before '{'; conversely, '{[(])}' has equal counts of each type yet fails because '(' was opened most recently while ']' arrived to close first. This exact last-opened/first-closed structure is LIFO.
[HI] वैध कोष्ठक नेस्टिंग में सबसे अंत में खुला कोष्ठक सबसे पहले बंद होना चाहिए। उदाहरणार्थ '{[()]}' सही है क्योंकि '(' पहले बंद होता है, फिर '[' और अंत में '{'; जबकि '{[(])}' में संख्या बराबर होने पर भी क्रम उल्टा होने से यह असंतुलित है। यही 'Last-Opened, First-Closed' व्यवहार स्टैक का LIFO सिद्धांत है।
2. Three-Step Stack Checking Algorithm (स्टैक द्वारा कोष्ठक जांच का तीन-चरणीय एल्गोरिथ्म)
[EN] Scan the string from index 0 to n - 1: (1) If ch is an opening bracket ('(', '{', '['), push it onto the stack; (2) If ch is a closing bracket (')', '}', ']'), first check if (isEmpty()) return false (extra closing delimiter), else pop top = pop() and return false unless (top, ch) form a matching pair; (3) Ignore all non-bracket characters (letters, digits, operators). Finally, after the loop ends, return isEmpty().
[HI] स्ट्रिंग को बाएं से दाएं स्कैन करें: (1) खुलने वाला कोष्ठक ('(', '{', '[') मिले तो स्टैक में पुश करें; (2) बंद होने वाला कोष्ठक (')', '}', ']') मिले तो यदि स्टैक खाली हो तो false लौटाएं, अन्यथा टॉप पॉप करके जांचें कि जोड़ी मेल खाती है या नहीं; (3) अन्य अक्षरों/अंकों को अनदेखा करें। लूप खत्म होने पर यदि स्टैक खाली (isEmpty()) हो तभी true लौटाएं।
3. Three Distinct Error Cases & Edge Conditions (तीन प्रमुख त्रुटि स्थितियाँ और विशेष केस)
[EN] A complete checker catches three distinct failure classes: (a) Excess closing bracket causing empty-stack underflow, e.g., '())' or ']'; (b) Mismatched bracket types, e.g., '(]' or '([)]'; and (c) Unclosed opening brackets left on the stack after the loop, e.g., '((()'—which is caught ONLY by the final return isEmpty() check! Note that an empty string '' or 'a + b' (no brackets) leaves an empty stack and returns true (balanced).
[HI] यह एल्गोरिथ्म तीन प्रकार की त्रुटियाँ पकड़ता है: (a) अतिरिक्त बंद कोष्ठक (जैसे '())') जहाँ खाली स्टैक पर पॉप करना पड़े; (b) बेमेल जोड़ी (जैसे '(]' या '([)]'); और (c) अंत में बचे खुले कोष्ठक (जैसे '((()') जिन्हें केवल अंतिम isEmpty() जांच पकड़ती है। खाली स्ट्रिंग '' या बिना कोष्ठक वाला व्यंजक संतुलित (true) माना जाता है।
4. Complexity & O(1)-Space Single-Bracket Optimization (कॉम्प्लेक्सिटी और एकल-कोष्ठक O(1) स्पेस अनुकूलन)
[EN] For mixed bracket types (), {}, [], worst-case time is O(n) and worst-case space is O(n) (e.g., an input of n '(' characters pushes all n items; valid '((()))' reaches depth n/2). However, if ONLY ONE bracket type '(' and ')' exists, a single integer counter (increment on '(', decrement on ')', abort if count < 0, require final count == 0) solves it in O(1) space! For multiple bracket types, counters fail on '([)]', making a Stack mandatory.
[HI] मिश्रित कोष्ठकों (), {}, [] के लिए टाइम और वर्स्ट-केस स्पेस दोनों O(n) होते हैं। किंतु यदि स्ट्रिंग में केवल एक ही प्रकार के कोष्ठक '(' और ')' हों, तो स्टैक की बजाय एक पूर्णांक काउंटर (जो '(' पर +1, ')' पर -1 हो और कभी <0 न जाए) से O(1) स्पेस में जांच हो सकती है; लेकिन अनेक प्रकार होने पर काउंटर '([)]' पर विफल हो जाता है, इसलिए स्टैक जरूरी है।
Syntax, Formula & Technical Example (Balanced Parentheses Checking Algorithm using Stack)
int match(char o, char c) { return (o=='('&&c==')')||(o=='{'&&c=='}')||(o=='['&&c==']'); }
int isBalanced(const char *s) {
char st[1000]; int top = -1;
for (int i = 0; s[i] != '\0'; i++) {
if (s[i]=='('||s[i]=='{'||s[i]=='[') st[++top] = s[i];
else if (s[i]==')'||s[i]=='}'||s[i]==']')
if (top == -1 || !match(st[top--], s[i])) return 0;
}
return top == -1;
}
Balanced Parentheses Checking Algorithm using Stack Quick Reference & Comparison Table
| Input Token / Case | Stack Action & Check | Failure Caught |
|---|---|---|
| Opening Bracket (, {, [ | Push character onto Stack | Max depth reaches O(n) on unclosed prefixes |
| Closing Bracket ), }, ] | Return false if empty OR popped opener mismatches | Catches extra ')' and cross-nested '([)]' |
| End-of-String Check | Return true strictly iff stack.isEmpty() is true | Catches leftover unclosed openers like '((()' |
| Single-Type Optimization | Integer counter tracks '(' only; O(1) extra space | Fails on mixed types like '([)]' without Stack |
Balanced Parentheses Checking Algorithm using Stack Top 20 Bilingual MCQs with Answers
Q1. Why is a Stack the ideal data structure for checking Balanced Parentheses across (), {}, and []?
((), {} और [] कोष्ठकों का संतुलन जांचने के लिए स्टैक को सबसे उपयुक्त डेटा संरचना क्यों माना जाता है?)
(A) Because brackets must always close in First-In, First-Out (FIFO) order
(B) Because stacks automatically sort brackets alphabetically
(C) Because the most recently opened bracket must always match the next closing bracket (LIFO)
(D) Because stacks eliminate the need to scan the string
Correct Answer: (C)
[EN] Nested delimiters follow Last-In, First-Out pairing: the innermost unclosed opening bracket sits on top of the stack to match first.
[HI] नेस्टेड कोष्ठकों में जो कोष्ठक सबसे अंत में खुलता है, वह सबसे पहले बंद होना चाहिए—जो सीधे स्टैक के LIFO सिद्धांत से मेल खाता है।
Q2. What happens if the input is '((()' and the algorithm mistakenly ends with 'return true;' instead of 'return isEmpty();'?
(यदि इनपुट '((()' हो और एल्गोरिथ्म लूप के बाद 'return isEmpty();' लिखने की बजाय सीधे 'return true;' कर दे, तो क्या होगा?)
(A) It throws Stack Underflow
(B) It reverses the string automatically
(C) It catches the error during the loop anyway
(D) It wrongly reports '((()' as balanced because unclosed '(' items remain on the stack
Correct Answer: (D)
[EN] No closing mismatch ever occurred inside the loop, so ONLY checking isEmpty() at the end detects leftover unclosed opening brackets.
[HI] लूप के अंदर कोई गलत बंद कोष्ठक नहीं आया, इसलिए अंत में बिना isEmpty() जांचे बचे हुए '(' नहीं पकड़े जाएंगे और गलत true परिणाम आएगा।
Q3. Which error fails immediately on the very first character of the string '])()'?
(स्ट्रिंग '])()' की जांच करते समय सबसे पहले अक्षर ']' पर ही कौन सी त्रुटि पकड़ी जाती है?)
(A) Stack Underflow / Empty-stack check (closing bracket encountered while stack is empty)
(B) Stack Overflow
(C) Type mismatch between '(' and ']'
(D) Leftover unclosed opening brackets at end
Correct Answer: (A)
[EN] The first character ']' is a closing bracket while the stack is empty (top == -1), immediately returning false.
[HI] पहला वर्ण ']' बंद करने वाला कोष्ठक है जबकि स्टैक अभी खाली (top == -1) है, जिससे पहले ही चरण में असंतुलन पकड़ा जाता है।
Q4. Why does using three separate integer counters (one each for (), {}, and []) FAIL to validate '([)]'?
((), {}, [] के लिए तीन अलग-अलग गिनती काउंटर रखना '([)]' की जांच करने में विफल क्यों हो जाता है?)
(A) Integer counters overflow above length 3
(B) Counters verify equal open/close counts per type, ignoring invalid interleaved crossing order
(C) Counters run in O(n^2) time
(D) Counters cannot handle non-bracket letters
Correct Answer: (B)
[EN] In '([)]', both '(' / ')' and '[' / ']' balance out to 0 individually, yet they cross illegally; only a Stack tracks order.
[HI] '([)]' में दोनों प्रकार के खुलने और बंद होने की संख्या बराबर है, इसलिए अलग-अलग काउंटर इसे सही मान बैठेंगे; क्रम की जांच केवल स्टैक कर सकता है।
Q5. Which of the following bracket strings is VALIDLY balanced?
(निम्नलिखित में से कौन सी कोष्ठक स्ट्रिंग पूरी तरह संतुलित (Validly Balanced) है?)
(A) {[(])}
(B) ][()
(C) {[()()]}[]
(D) ((())
Correct Answer: (C)
[EN] Every opener closes cleanly in reverse order inside {[()()]}[], leaving the stack empty at the end.
[HI] {[()()]}[] में प्रत्येक खुलने वाला कोष्ठक सही क्रम में बंद होता है और अंत में स्टैक खाली हो जाता है।
Q6. What is the MAXIMUM number of elements simultaneously on the stack while checking '(((())))' vs '()()()()'?
('(((())))' और '()()()()' को जांचते समय स्टैक पर एक साथ अधिकतम कितने कोष्ठक रहेंगे?)
(A) 4 for '(((())))' and 1 for '()()()()'
(B) 4 for both strings
(C) 1 for '(((())))' and 4 for '()()()()'
(D) 8 for '(((())))' and 4 for '()()()()'
Correct Answer: (A)
[EN] '(((())))' pushes 4 '(' before popping; '()()()()' pushes 1 '(' and immediately pops it before the next '(' arrives.
[HI] '(((())))' में चार '(' लगातार पुश होने से अधिकतम आकार 4 होगा, जबकि '()()()()' में हर '(' तुरंत पॉप हो जाने से आकार 1 रहेगा।
Q7. What should isBalanced("") (an empty string) or isBalanced("a + b * c") (zero brackets) return?
(खाली स्ट्रिंग "" या बिना कोष्ठक वाली स्ट्रिंग "a + b * c" पर संतुलित कोष्ठक एल्गोरिथ्म क्या लौटाएगा?)
(A) false (Unbalanced)
(B) Stack Underflow error
(C) Null pointer exception
(D) true (Balanced)
Correct Answer: (D)
[EN] Zero opening brackets and zero mismatched closings leave the stack empty at termination, satisfying balanced criteria.
[HI] कोई भी बंद या खुला कोष्ठक शेष न रहने से अंत में स्टैक खाली मिलता है, अतः परिणाम true (संतुलित) आता है।
Q8. When checking the arithmetic expression '(a + [b * {c - d}])', what is stored in the stack just before reading '}'?
(व्यंजक '(a + [b * {c - d}])' की जांच में '}' पढ़ने से ठीक पहले स्टैक में नीचे से ऊपर कौन से वर्ण मौजूद रहेंगे?)
(A) ['{'] only
(B) ['{', '[', '(']
(C) ['(', '[', '{']
(D) ['(', 'a', '+', '[', 'b', '*', '{']
Correct Answer: (C)
[EN] Non-bracket characters ('a', '+', 'b', '*', 'c', '-', 'd') are ignored; only opening brackets '(', '[', '{' sit on the stack.
[HI] अक्षर व अंक ('a', '+', आदि) स्टैक में नहीं जाते; केवल खुले कोष्ठक नीचे से ऊपर ['(', '[', '{'] रहते हैं।
Q9. For a valid string of ONLY single-type parentheses '()' of length n, what extra space complexity suffices without a Stack?
(यदि स्ट्रिंग में केवल एक ही प्रकार के कोष्ठक '(' और ')' हों, तो बिना स्टैक के कितनी अतिरिक्त स्पेस कॉम्प्लेक्सिटी में जांच हो सकती है?)
(A) O(n) space always
(B) O(log n) space
(C) O(1) space (using a single integer depth counter)
(D) O(n^2) space
Correct Answer: (C)
[EN] A single counter tracking unclosed '(' count needs only O(1) memory, rejecting immediately if counter drops below 0.
[HI] एकल प्रकार के लिए केवल एक पूर्णांक काउंटर पर्याप्त है, जिसमें O(1) स्थिर स्पेस लगता है।
Q10. What is the worst-case time and space complexity of Balanced Parentheses Checking on mixed (), {}, [] of length n?
(n लंबाई वाली मिश्रित कोष्ठक स्ट्रिंग (), {}, [] की जांच की वर्स्ट-केस टाइम और स्पेस कॉम्प्लेक्सिटी क्या है?)
(A) O(log n) time and O(n) space
(B) O(n^2) time and O(n) space
(C) O(n) time and O(1) space
(D) O(n) time and O(n) space
Correct Answer: (D)
[EN] Every character is examined once (O(n) time), and an input of n opening brackets pushes n items onto the stack (O(n) space).
[HI] प्रत्येक वर्ण एक बार जांचा जाता है (O(n) समय), और यदि सभी n वर्ण खुलने वाले हों तो स्टैक में n तत्व आ सकते हैं (O(n) स्पेस)।
Q11. How many distinct valid balanced parentheses combinations exist for n = 3 pairs of '(' and ')'?
(3 जोड़ी '(' और ')' कोष्ठकों (कुल 6 वर्णों) से कुल कितने अलग-अलग वैध संतुलित संयोजन बनाए जा सकते हैं?)
(A) 5 (the 3rd Catalan number: ((())), (()()), (())(), ()(()), ()()())
(B) 6
(C) 3
(D) 8
Correct Answer: (A)
[EN] The count of valid balanced n-pair strings equals the nth Catalan number C_n = (2n)! / ((n+1)! n!); for n = 3, C_3 = 5.
[HI] n जोड़ी वैध कोष्ठकों की संख्या कैटलन संख्या C_n होती है; n = 3 के लिए C_3 = 5 वैध संयोजन बनते हैं।
Q12. What happens inside the loop on '(}' when '}' is encountered?
(स्ट्रिंग '(}' में '}' मिलने पर स्टैक एल्गोरिथ्म किस शर्त के कारण असफल होकर false लौटाता है?)
(A) Popped top '(' does not match closing '}'
(B) Stack is empty when '}' arrives
(C) Stack overflows before '}' arrives
(D) Algorithm reaches end of string with leftover '{'
Correct Answer: (A)
[EN] Popping '(' and comparing pair ('(', '}') fails the bracket-type equality check immediately.
[HI] स्टैक से '(' पॉप होता है, जो '}' की सही जोड़ी नहीं है—अतः टाइप मिसमैच के कारण तुरंत false लौटता है।
Q13. Which real-world software task directly uses a variant of the Stack-based Balanced Delimiter algorithm?
(वास्तविक जीवन के किस सॉफ्टवेयर कार्य में स्टैक-आधारित कोष्ठक संतुलन एल्गोरिथ्म का प्रत्यक्ष उपयोग होता है?)
(A) Disk defragmentation block sorting
(B) CPU L1 hardware cache line eviction
(C) Compiler syntax parsing and HTML/XML opening-closing tag validation
(D) IPv4 subnet mask calculation
Correct Answer: (C)
[EN] Compilers match braces/brackets in source code and HTML/XML parsers push <tag> and match </tag> on a Stack.
[HI] कंपाइलर के सिंटैक्स पार्सर और HTML/XML टैग (<tag>...</tag>) मिलान करने वाले टूल्स सीधे इसी स्टैक तकनीक का उपयोग करते हैं।
Q14. If a string of length n = 7 consists purely of brackets '((()))(', can it EVER be balanced?
(यदि 7 वर्णों (विषम लंबाई) वाली एक कोष्ठक स्ट्रिंग '((()))(' हो, तो क्या वह कभी भी संतुलित हो सकती है?)
(A) Yes, if checked from right to left
(B) Yes, if rotated once to the right
(C) Yes, because '(' count exceeds ')' by 1
(D) No — any string containing an odd number of brackets can never be balanced
Correct Answer: (D)
[EN] Every balanced pair consumes 2 brackets (one open, one close), so total bracket count MUST be even.
[HI] प्रत्येक वैध जोड़े में 2 कोष्ठक (1 खुला, 1 बंद) होते हैं, इसलिए विषम संख्या वाले कोष्ठकों की स्ट्रिंग कभी संतुलित नहीं हो सकती।
Q15. What is the minimum number of bracket reversals needed to balance the string '}}{{', using a stack to cancel valid pairs first?
(अमान्य स्ट्रिंग '}}{{' को संतुलित करने के लिए न्यूनतम कितने कोष्ठक पलटने (Reversals) पड़ेंगे?)
(A) 2 reversals (flipping first '}' to '{' and last '{' to '}' gives '{}{}')
(B) 1 reversal
(C) Impossible to balance
(D) 4 reversals
Correct Answer: (A)
[EN] No valid '{}' pairs cancel in '}}{{'. With m = 2 unmatched '}' and n = 2 unmatched '{', formula ceil(m/2) + ceil(n/2) = 1 + 1 = 2.
[HI] यहाँ 2 असंतुलित '}' और 2 असंतुलित '{' बचते हैं; सूत्र ceil(m/2) + ceil(n/2) = 1 + 1 = 2 बार पलटने से '{}{}' संतुलित हो जाता है।
Q16. Which statement is NOT true regarding Balanced Parentheses Checking using a Stack?
(स्टैक द्वारा संतुलित कोष्ठक जांच के विषय में कौन सा कथन असत्य (NOT true) है?)
(A) Ignoring the final isEmpty() check still correctly detects inputs like '((()'
(B) Popping from an empty stack on a closing bracket immediately returns false
(C) A Stack is strictly required when checking multiple types like (), {}, [] together
(D) Non-bracket characters inside expressions are skipped without modifying the stack
Correct Answer: (A)
[EN] Omitting the final isEmpty() check fails completely on strings that open brackets without closing them (like '((()').
[HI] अंत में isEmpty() की जांच न करने पर '((()' जैसे अधूरे खुले कोष्ठक वाले इनपुट नहीं पकड़े जा सकते।
Q17. Within Balanced Parentheses Checking Algorithm using Stack, which input token / case directly maps to: "Push character onto Stack"?
(Balanced Parentheses Checking Algorithm using Stack में कौन सा Input Token / Case सीधे "Push character onto Stack" से संबंधित है?)
(A) End-of-String Check
(B) Closing Bracket ), }, ]
(C) Single-Type Optimization
(D) Opening Bracket (, {, [
Correct Answer: (D)
[EN] In Balanced Parentheses Checking Algorithm using Stack, 'Opening Bracket (, {, [' handles 'Push character onto Stack' (Max depth reaches O(n) on unclosed prefixes).
[HI] Balanced Parentheses Checking Algorithm using Stack में 'Opening Bracket (, {, [' का कार्य/विवरण 'Push character onto Stack' (Max depth reaches O(n) on unclosed prefixes) है।
Q18. Which option accurately describes 'Closing Bracket ), }, ]' in Balanced Parentheses Checking Algorithm using Stack?
(Balanced Parentheses Checking Algorithm using Stack के संदर्भ में 'Closing Bracket ), }, ]' की सही विशेषता कौन सी है?)
(A) Push character onto Stack
(B) Return false if empty OR popped opener mismatches
(C) Return true strictly iff stack.isEmpty() is true
(D) Integer counter tracks '(' only; O(1) extra space
Correct Answer: (B)
[EN] 'Closing Bracket ), }, ]' provides 'Return false if empty OR popped opener mismatches' — key point: Catches extra ')' and cross-nested '([)]'.
[HI] 'Closing Bracket ), }, ]' का मुख्य विवरण 'Return false if empty OR popped opener mismatches' है (Catches extra ')' and cross-nested '([)]')।
Q19. In Balanced Parentheses Checking Algorithm using Stack, identify the correct parameter for the specification: "Return true strictly iff stack.isEmpty() is true".
(Balanced Parentheses Checking Algorithm using Stack में "Return true strictly iff stack.isEmpty() is true" विवरण किस विकल्प के लिए सही है?)
(A) End-of-String Check
(B) Single-Type Optimization
(C) Closing Bracket ), }, ]
(D) Opening Bracket (, {, [
Correct Answer: (A)
[EN] 'End-of-String Check' corresponds to 'Return true strictly iff stack.isEmpty() is true' (Catches leftover unclosed openers like '((()').
[HI] 'End-of-String Check' का संबंध 'Return true strictly iff stack.isEmpty() is true' (Catches leftover unclosed openers like '((()') से है।
Q20. Considering Balanced Parentheses Checking Algorithm using Stack, what key behavior defines 'Single-Type Optimization'?
(Balanced Parentheses Checking Algorithm using Stack में 'Single-Type Optimization' की मुख्य भूमिका या मान क्या है?)
(A) Integer counter tracks '(' only; O(1) extra space
(B) Return true strictly iff stack.isEmpty() is true
(C) Return false if empty OR popped opener mismatches
(D) Push character onto Stack
Correct Answer: (A)
[EN] 'Single-Type Optimization' represents 'Integer counter tracks '(' only; O(1) extra space' (Fails on mixed types like '([)]' without Stack).
[HI] 'Single-Type Optimization' का अर्थ/मान 'Integer counter tracks '(' only; O(1) extra space' है (Fails on mixed types like '([)]' without Stack)।
Balanced Parentheses Checking Algorithm using Stack — Exam FAQs
Q1: Can Balanced Parentheses checking handle HTML tags like <div><p></p></div> using the same Stack idea?
क्या इसी स्टैक विधि से <div><p></p></div> जैसे HTML टैग्स का संतुलन भी जांचा जा सकता है?
[EN] Yes! Instead of pushing single characters, push opening tag names ('div', 'p') onto the stack and verify that each closing tag ('/p', '/div') matches the popped top.
[HI] हाँ! अक्षरों की जगह खुलने वाले टैग नाम ('div', 'p') स्टैक में पुश किए जाते हैं और बंद टैग ('/p', '/div') आने पर टॉप से मिलान किया जाता है।
Q2: What if brackets appear inside string literals like printf("(") in a real C compiler?
वास्तविक C कंपाइलर में यदि printf("(") जैसी स्ट्रिंग के अंदर कोष्ठक आए तो क्या होता है?
[EN] A compiler's lexical analyzer first strips comments and string/character literals into tokens so brackets inside quotes are ignored by syntax delimiter matching.
[HI] कंपाइलर का लेक्सिकल एनालाइजर पहले स्ट्रिंग लिटरल और कमेंट्स को अलग टोकन बना देता है, जिससे कोट्स के अंदर का कोष्ठक सिंटैक्स जांच को प्रभावित नहीं करता।
Q3: Why is O(n/2) often cited as space complexity for valid balanced strings?
अक्सर वैध संतुलित स्ट्रिंग के लिए स्पेस कॉम्प्लेक्सिटी O(n/2) क्यों बोली जाती है?
[EN] For a balanced string of length n, at most n/2 brackets can be unclosed openers before closing brackets must appear (e.g., n/2 '(' followed by n/2 ')'); in Big-O notation O(n/2) simplifies to O(n).
[HI] संतुलित स्ट्रिंग में अधिकतम n/2 कोष्ठक ही खुल सकते हैं वरना बाकी बंद करने के लिए स्थान नहीं बचेगा; बिग-ओ में O(n/2) को O(n) लिखा जाता है।
Post a Comment
Post a Comment