Scribd
Upload
2 views6 pages

Stack Problems

The document outlines four programming problems involving string manipulation and matrix operations. The first problem focuses on decoding an encoded string, the second on finding the longest valid substring of parentheses, the third on identifying a celebrity in a party using a matrix representation, and the fourth on processing a string with backspaces represented by '#'. Each problem includes input/output examples and constraints.

Uploaded by

Piyush Trivedi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views6 pages

Stack Problems

The document outlines four programming problems involving string manipulation and matrix operations. The first problem focuses on decoding an encoded string, the second on finding the longest valid substring of parentheses, the third on identifying a celebrity in a party using a matrix representation, and the fourth on processing a string with backspaces represented by '#'. Each problem includes input/output examples and constraints.

Uploaded by

Piyush Trivedi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Problem Solving Using Stack

Dr. Rajesh Kumar Panda


KIIT Deemed to be University
Q1. An encoded string (s) is given, the task is to decode it. The pattern
in which the strings were encoded were as follows.
original string: abbbababbbababbbab
encoded string : "3[a3[b]1[ab]]".
Input:The first line of input contains an integer T denoting the no of
test cases. Then T test cases follow. Each test case contains a string
s.
Output:For each test case in a new line print the required decoded
string.
Constraints:1<=T<=101<=length of the string <=30
Example:Input:
2
2[b]
3[b2[ca]]
Output:
bb
bcacabcacabcaca
Q2. Length of the longest valid substring
Given a string consisting of opening and
closing parenthesis, find length of the longest
valid parenthesis substring.
Examples:
Input : ((() Output : 2 Explanation : ()
Input: )()()) Output : 4 Explanation: ()()
Input: ()(())))) Output: 6 Explanation: ()(())
Q3. You are in a party of N people, where only
one person is known to everyone. Such a
person may be present in the party, if yes,
(s)he doesn’t know anyone in the party. Your
task is to find the stranger (celebrity) in
[Link] will be given a square matrix M[][]
where if an element of row i and column j is
set to 1 it means ith person knows jth person.
You need to write a program which finds the
id of the celebrity if present else return -1.
Note: Expected time complexity is O(N) with
constant extra space.
Input:The first line of input contains an element
T denoting the number of test cases. Then T
test cases follow. Each test case consist of 2
lines. The first line of each test case contains a
number denoting the size of the matrix M.
Then in the next line are space separated
values of the matrix M.
Output:For each test case output will be the id
of the celebrity if present (0 based index). Else
-1 will be printed.
Q4. Given a string S containing letters and ‘#‘.
The ‘#” represents a backspace. The task is to
print the new string without ‘#‘.
Examples:
Input : S = "abc#de#f#ghi#jklmn#op#"
Output : abdghjklmo

You might also like