Strings: Permutations of a given string
Problem Statement: You are given a string, you need to find all the permutations of it. Example Input: abc Output: ABC ACB BAC BCA CBA CAB Solution To solve this problem we shall use the concept of backtracking. Here we will swap each of the characters in the string with the first character. Then we […]
Strings: Given a string, print all the subsequence
Problem Statement: You are given a string, you need to find all the subsequence of it. A subsequence in a string is generated by deleting someof the characters without changing it’s order. Example Input: abc Output: a, b, c, ab, bc, ac, abc Solution The solution is very simple. We use recursion technique. Solution in […]
Strings: Longest Repeating Subsequence
Problem Statement: Given a string find the length of the longest repeating sub sequence. Here we need to find the sub sequence, not sub string. Hence sub sequence need not require to occupy consecutive positions. You need to find that sub sequence, such that the two sub sequence don’t have same string character at same […]
Strings: Program to check if strings are rotations of each other or not
Problem Statement: Given 2 strings str1 and str2, you need to write a program to check if s2 is a rotation of s1. Example str1 = ABCD str2 = CDAB Output: true Solution Solution is very simple, we will concatenate the first string with itself. Then we will check if the second string is present […]
Strings: Print all the duplicates in a string
Problem Statement: Given a string, get all the duplicates and print their count. Example String: helloo l = 2 o = 2 Solution Solution is very simple. Take an array whose size is 256. Then initialize it to 0. Then convert the character into its ascii value and increment the count at that index. Print […]
Strings: Reverse a string
Problem Statement: Given an array of characters reverse them in-place without taking extra space. Example Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Solution The solution is very simple. Take 2 pointers, first pointer pointing to the start of the array. second pointer pointing at the end of the array. Then swap the elements and increase first pointer and […]
Matrix: Get the common elements in all row of a matrix.
Problem Statement: You are given an m*n matrix, you need to print all the common elements present in all the rows. Example: mat[4][5] = {{1, 2, 1, 8}, {3, 7, 8, 5}, {8, 7, 7, 3}, {8, 1, 2, 7}, }; Output: 8 Solution In this solution we will use MAPS. Initially insert all the […]
Matrix: Kth smallest element in a sorted matrix
Problem Statement: You are given n*n matrix, where every row and column is sorted in non descending order. You need to find kth smallest element in the given 2D array. Example Input: k = 3 array = 10, 20, 30, 40 50, 60, 70, 80 90, 100, 110, 120 130, 140, 150,160 Output: 30 Explanation: […]
Matrix: Find a row with maximum number of 1’s in a binary matrix
Problem Statement: You are given a m*n binary matrix, you need to find a row that has maximum number of 1’s in it. Each row in the matrix is sorted. Example: Input matrix 0 0 1 1 0 0 1 1 1 1 1 1 // this row has maximum number of 1s 0 0 […]
Matrix: Find median in a row wise sorted matrix.
Problem Statement: You are given a row-wise sorted matrix of size r*c. You need to find the median of the matrix. Example: Input : 1 3 5 2 6 9 3 6 9 Now put all the values in sorted order. arr [] = 1 2 3 3 5 6 6 9 9 From this […]