Hi Peeps,
Welcome back to LetsAlgo. Today I will be listing down the top string problems which are most frequently asked in interviews.
Like arrays, string is one of the most frequently used data structures in day-to-day application development. Hence it becomes quite necessary to have a good understanding of it.
String is a linear collection of characters, which forms a valid word or sentence together.
Questions related to string are mostly about re-arranging characters or comparing subsequences.
So below are the few basic strings problems mostly asked in interviews.
1) Reverse string
Let’s start with the most basic problem of strings, this problem is asked mostly in campus placement interviews. It tests your understanding with indexes in strings.
Problem Statement:
You are given string str. Your task is not to reverse it.
Code:
string reverseWord(string str){
int left = 0;
int right = str.length() — 1;
while(left<right) {
swap(str[left++],str[right–]);
}
return str;
}
Brief :
To solve this problem, we simply take two pointers left and right. left holds the starting index of the input string whereas right holds the last index.
We run while loop till left is smaller than right and in each iteration, we swap element at left with the element at right and we increase left by 1 and decrease right by 1.
For a detailed article about this problem, please click here.
2) String rotation
String rotation is another basic problem of strings, which is asked to freshers as well as experienced developers in their interviews.
This problem consists of two strings and you return the bool value as output.
Problem statement:
You are given two string s1 and s2. Your task is to find out whether s1 and s2 are rotations of each other or not.
Code:
bool isRotation(string s1, string s2)
{
if (s1.length() != s2.length())
return false;
string temp = s1+s1;
return (temp.find(s2) != string::npos);
}
Brief:
There can be multiple ways of solving this problem but the easiest as fastest would be :
we take a temp string and initialize it with s1+s1 and then check if temp contains s2 or not.
As any rotation of s1 will be present in temp.
For a detailed article about this problem, please click here.
3) String palindrome
Problems related to palindrome are the most frequently asked strings problems. A string is said to be a palindrome if the string read from left to right is equal to the string read from right to left.
Problem statement:
You are given a string s. Your task is to find whether s is a palindromic string or not.
Code:
bool isPalindrome(string s)
{
int left = 0;
int right = s.length() — 1;
while(left<right) {
if (s[left] != s[right]) {
return false;
}
left++;
right–;
}
return true;
}
Brief:
To check whether a given string is palindromic or not, we use two pointers, left and right. left has an initial value of 0 and right has an initial value equal to the last index of the input string.
we run while loop till left is smaller than right. On every iteration, we check if char at left is the same as char at right. if true, then we increase left and decrease right. If char at left is not equal to char at right, then we simply return false, because we get to know the string is not palindromic.
For a detailed article about this problem, please click here.
4) Print all duplicates in string
This problem is another straightforward problem of string, which has been asked multiple times in interviews.
This problem requires you to have a basic understanding of the map or dictionary.
Problem statement:
You are given a string S, your task is to print all duplicate characters along with their occurrence.
Code:
void printDuplicates(string s)
{
map<char, int> count;
for (int i = 0; i < s.length(); i++) {
count[s[i]]++;
}
for (auto el : count) {
if (el.second > 1)
cout << el.first << “: “ << el.second
<< “\n”;
}
}
Brief:
To print all duplicates, we simply take a map <char, int>. This map will store all unique characters of input string as key and their occurrence as the value against those key.
To fill the map, we will iterate through all characters of the input string.
Once our map is filled, we will simply run another loop on all keys of the map.
On every iteration, we will check if the value against the current key is greater than 1, if yes then we will print the key (character) and its value (no, of occurrence).
For a detailed article about this problem, please click here.
5) Longest palindromic string
This problem is not as simple as above problems we just discussed. Hence it’s difficulty level can be considered as medium.
Although this problem can be easily solved with three nested loops, but that won’t be an efficient solution. So I hardly recommend you to read the dedicated article of this problem to understand its pyramid of doom. Link is given below.
Problem statement:
You are given a string s. Your task is to find the longest palindrome substring.
Code:
int findBiggestFromCenter(string s, int left, int right) {
while(left>= 0 && right < s.length() && s[left] == s[right]) {
left–;
right++;
}
return right-1-left;
}
string longestPalindrome (string s) {
if ( !s.empty() && s.length() <= 1 )
return s;
int len = 0, start = 0, end = 0, len1 = 0, len2 = 0;
for (int i = 0; i<= s.length(); i++) {
len1 = findBiggestFromCenter(s,i,i);
len2 = findBiggestFromCenter(s,i,i+1);
len = max(len1,len2);
if (len > end — start) {
start = i — (len-1)/2;
end = i + len/2;
}
}
return s.substr(start, end);
}
Brief:
To get the longest palindromic string, we are required two methods.
First would be the main method named findBiggestFromCenter, which iterates through characters of the input string.
This method will subsequently call the helper method named longestPalindrome.
longestPalindrome will return the range of longest palindromic around the given character.
Please note that we call method longestPalindrome twice for each character. The reason for doing so is, there could be an even length palindromic string as well as an odd length palindromic string, around one character.
So we simply find the length of both types of palindromic string.
In findBiggestFromCenter, we will compare the returned ranges and find the longest one, and then we compare the longest range with the existing longest range we already have.
If the returned range is greater than the existing, then we update the existing range.
PS: By range I mean, two integer values, which denotes the start and end of the palindromic string.
Existing ranges are being denoted by start and end variables in the program.
For a detailed article about this problem, please click here.
Thats all from my side for this article. Thanks a lot for reading it.
Keep coding.
ByeByeee
