Given an encoded string, decode string
Problem Statement: You are given an encoded string, you need to decode it. Example Input: s = “3[a]2[bc]” Output: “aaabcbc” Solution To solve this problem, we will use 2 stacks. One stack will hold the number Another stack will hold the letters If we have a string “3[a]2[bc]” Initially the digit will be put into […]
Calculate an expression with * and /
Problem Statement: You are given a string, that has a valid expression. You need to implement a calculator and evaluate it. String will consist of +’, ‘-‘, ‘*’, ‘/’. Solution In this question we have to prioritize the operation of “* and /” We will use a temp variable that will calculate the intermediate result. […]
Calculate the basic arithmetic expression as string
Problem Statement: You are given a string, that has a valid expression. You need to implement a basic calculator and evaluate it. String will consist of ‘+’, ‘-‘, ‘(‘, ‘)’, and ‘ ‘. Example Input: str = “1 + 1” output: 2 Solution We will use stack for this problem. So based on the input, […]
Stack: Get the min element of the stack in O(1) time
Problem Statement: You need to implement a stack that will return the min element in constant time. Solution This problem can be solved in 2 ways: 1. Using 2 stacks 2. Using only 1 stack. Method 1: Using 2 stacks: In this method, we maintain 2 stacks. One stack to insert all the elements and […]
Dynamic Programming: Get the count of delete operations on 2 strings.
Problem Statement: You are given 2 strings, you need to return the minimum number of delete operations needed to make str1 and str 2 same. Example Input: str1 = “sea”, str2 = “eat” Output: 2 Delete one char from “sea” to “ea”, then delete one char from “eat” to “ea” Solution From the above explanation, […]
Dynamic Programming: Longest Common Substring
Problem Statement: You are given 2 strings, you need to find the longest common substring. Example Example: str 1 = abcdef str 2 = bcxyez Output: 2 Here the number of substring possible are: {b, c} {e} The characters should be continuous then it is a substring. So by looking at the above definition we […]
Dynamic Programming: Count how many times string 1 appears as substring in string 2.
Problem Statement: You are given 2 strings, you need to find how many times string 2 appears as subsequence in string 1. Example string = “subsequence” pattern = “ue” Output: 4 subsequence – – subsequence – – subsequence – – subsequence — subsequence – – Solution The solution is similar to LCS problem Here we […]
Dynamic Programming: Check if one string is a subsequence of another
Problem Statement: Youa are given 2 strings, a, b. You need to check if string “a” is a subsequence of string “b” Example Input: str1 = “abc” str2 = “ahbgdc” Output: true “abc” is a subsequence of str2. Solution The solution is straight forward. You need to find if there is any subsequence of str1 […]
Dynamic Programming: Longest repeating subsequence
Problem Statement: You are given a string, you need to find the length of the longest repeating subsequence. Example Input: AABEBCDD O/p: 3 Here the longest repeating subsequence is : ABD Solution What we will do is, we will get the LCS of the string itself with a condition being, if both the characters are […]
Dynamic Programming: Minimum number of deletions and insertions to convert one string into another
Problem Statement: You are given 2 strings, you need to get the minimum number of insertions and deletions to convert string a to string b. Example Input: str1: heap str2: pea Minimum insertion: 1 Minimum deletions: 2 So first insert “p” to string 1. It will become “pheap”. Then delete “h p” then the string […]