Most important question of string with solution.
String
Check if a string is a rotated palindrome or not
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// Recursive function to check if `str[low…high]` is a palindrome or not
bool isPalindrome(string str, int low, int high)
{
return (low >= high) || (str[low] == str[high] &&
isPalindrome(str, low + 1, high - 1));
}
// Function to check if a given string is a rotated palindrome or not
bool isRotatedPalindrome(string str)
{
// length of the given string
int n = str.length();
// check for all rotations of the given string if it
// is palindrome or not
for (int i = 0; i < n; i++)
{
// in-place rotate the string by 1 unit
rotate(str.begin(), str.begin() + 1, str.end());
// rotate(str.rbegin(), str.rbegin() + 1, str.rend());
// return true if the rotation is a palindrome
if (isPalindrome(str, 0, n - 1)) {
return true;
}
}
// return false if no rotation is a palindrome
return false;
}
int main()
{
// palindromic string
string str = "ABCDCBA";
// rotate it by 2 units
rotate(str.begin(), str.begin() + 2, str.end());
if (isRotatedPalindrome(str)) {
cout << "The string is a rotated palindrome";
}
else {
cout << "The string is not a rotated palindrome";
}
return 0;
}
Longest Palindromic Substring Problem
#include <iostream>
#include <string>
using namespace std;
// Expand in both directions of `low` and `high` to find
// maximum length palindrome
string expand(string str, int low, int high)
{ int len = str.length();
// run till `str[low.high]` is a palindrome
while (low >= 0 && high < len && (str[low] == str[high])) {
low--, high++; // Expand in both directions
}
// return palindromic substring
return str.substr(low + 1, high - low - 1);
}
// Function to find the longest palindromic substring in `O(n²)` time
// and `O(1)` space
string findLongestPalindromicSubstring(string str, int len)
{
// `max_str` stores the maximum length palindromic substring
// found so far
string max_str = "", curr_str;
// `max_length` stores the maximum length of palindromic
// substring found so far
int max_length = 0, curr_length;
// consider every character of the given string as a midpoint and expand
// in both directions to find maximum length palindrome
for (int i = 0; i < len; i++)
{
// find the longest odd length palindrome with `str[i]` as a midpoint
curr_str = expand(str, i, i);
curr_length = curr_str.length();
// update maximum length palindromic substring if odd length
// palindrome has a greater length
if (curr_length > max_length)
{
max_length = curr_length;
max_str = curr_str;
}
// Find the longest even length palindrome with `str[i]` and `str[i+1]`
// as midpoints. Note that an even length palindrome has two
// midpoints.
curr_str = expand(str, i, i + 1);
curr_length = curr_str.length();
// update maximum length palindromic substring if even length
// palindrome has a greater length
if (curr_length > max_length)
{
max_length = curr_length;
max_str = curr_str;
}
}
return max_str;
}
int main()
{
string str = "ABDCBCDBDCBBC";
cout << "The longest palindromic substring of " << str << " is " << findLongestPalindromicSubstring(str, str.length() - 1);
return 0;
}
Output:
The longest palindromic substring of ABDCBCDBDCBBC is BDCBCDB
Check if a repeated subsequence is present in a string or not
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// Recursive function to check if `str[low…high]` is a palindrome or not
bool isPalindrome(string str, int low, int high)
{
// base case
if (low >= high) {
return true;
}
return (str[low] == str[high]) &&
isPalindrome(str, low + 1, high - 1);
}
// Function to checks if repeated subsequence is present
// in the string
bool hasRepeatedSubsequence(string str)
{
// map to store the frequency of each distinct character
// of a given string
unordered_map<char, int> freq;
// update map with frequency
for (int i = 0; i < str.length(); i++)
{
// if the frequency of any character becomes 3,
// we have found the repeated subsequence
if (++freq[str[i]] >= 3) {
return true;
}
}
string temp;
// consider all repeated elements (frequency 2 or more)
// and discard all non-repeating elements (frequency 1)
for (int i = 0; i < str.length(); i++)
{
if (freq[str[i]] >= 2) {
temp += str[i];
}
}
// return false if `temp` is a palindrome
return !isPalindrome(temp, 0, temp.length() - 1);
}
int main()
{
string str = "XYBYAXB"; // `XB` and `YB` are repeated subsequences
if (hasRepeatedSubsequence(str)) {
cout << "Repeated subsequence is present";
}
else {
cout << "No repeated subsequence is present";
}
return 0;
}
Output:
Repeated subsequence is present
Check if strings can be derived from each other by circularly rotating them
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// Function to check if `X` can be derived from `Y` by rotating it
bool check(string X, string Y)
{
int m;
// if string lengths are different, they can't be
// derived from each other
if ((m = X.length()) != Y.length()) {
return false;
}
// Invariant: At the i'th iteration of this loop,
// the string `X` will be rotated by `i` units
for (int i = 0; i < m; i++)
{
// in-place left rotates string `X` by 1 unit
rotate(X.begin(), X.begin() + 1, X.end());
// for right rotation, we can use reverse iterators.
// i.e., rotate(X.rbegin(), X.rbegin() + 1, X.rend());
// return true if `X` becomes equal to `Y`
if (!X.compare(Y)) {
return true;
}
}
// return false if no rotation is matched
return false;
}
int main()
{
string X = "ABCD";
string Y = "DABC";
if (check(X, Y)) {
cout << "Given strings can be derived from each other";
}
else {
cout << "Given strings cannot be derived from each other";
}
return 0;
}
Output:
Given strings can be derived from each other
Convert a number into a corresponding excel column name
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
// Function to convert a given number to an Excel column
string getColumnName(int n)
{
// initialize output string as empty
string result = "";
while (n > 0)
{
// find the index of the next letter and concatenate the letter
// to the solution
// here index 0 corresponds to `A`, and 25 corresponds to `Z`
int index = (n - 1) % 26;
result = char(index + 'A') + result;
n = (n - 1) / 26;
}
return result;
}
int main()
{
// seed for random input
srand(time(NULL));
// generate column names for 10 random numbers between 1–1000
for (int i = 1; i <= 10; i++)
{
int r = rand() % 1000 + 1;
cout << r << " — " << getColumnName(r) << endl;
}
return 0;
}
Output (will vary):
585 — VM
873 — AGO
269 — JI
849 — AFQ
288 — KB
962 — AJZ
549 — UC
572 — UZ
485 — RQ
704 — AAB
Determine whether two strings are anagram or not
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// Function to check if `X` and `Y` are anagrams or not
bool isAnagram(string X, string Y)
{
// if X's length is not the same as Y's, they can't be an anagram
if (X.length() != Y.length()) {
return false;
}
// create an empty map
unordered_map<int, int> freq;
// maintain a count of each character of `X` on the map
for (char x: X) {
freq[x]++;
}
// do for each character `y` of `Y`
for (char y: Y)
{
// if `y` is not found in the map, i.e., either `y` is not present
// in string `X` or has more occurrences in string `Y`
if (freq.find(y) == freq.end()) {
return false;
}
// decrease the frequency of `y` on the map
freq[y]--;
// if its frequency becomes 0, erase it from the map
if (!freq[y]) {
freq.erase(y);
}
}
// return true if the map becomes empty
return !freq.size();
}
int main()
{
string X = "tommarvoloriddle"; // Tom Marvolo Riddle
string Y = "iamlordvoldemort"; // I am Lord Voldemort
if (isAnagram(X, Y)) {
cout << "Anagram";
}
else {
cout << "Not an Anagram";
}
return 0;
}
Output:
Anagram
[ ] Wildcard
Given a binary pattern containing ? wildcard character at a few positions, find all possible combinations of binary strings that can be formed by replacing the wildcard character by either 0 or 1.
#include <iostream>
#include <stack>
using namespace std;
// Find all binary strings that can be formed from a given
// wildcard pattern
void printAllCombinations(string pattern)
{
// create an empty stack (we can also use set, queue, vector, or
// any other container)
stack<string> list;
list.push(pattern); // push the pattern into the stack
size_t index;
// loop till stack is empty
while (!list.empty())
{
// pop a string from the stack and process it
string curr = list.top();
list.pop();
// `index` stores position of the first occurrence of wildcard
// pattern in `curr`
if ((index = curr.find_first_of('?')) != string::npos)
{
for (int i = 0; i < 2; i++)
{
// replace `?` with 0 and 1 and push it into the stack
curr[index] = i + '0';
list.push(curr);
}
}
// if no wildcard pattern is found, print the string
else {
cout << curr << endl;
}
}
}
int main()
{
string str = "1?11?00?1?";
printAllCombinations(str);
return 0;
}
Output:
1111100111
1111100110
1111100011
1111100010
1111000111
1111000110
1111000011
1111000010
1011100111
1011100110
1011100011
1011100010
1011000111
1011000110
1011000011
1011000010
Find all interleaving of given strings
#include <iostream>
#include <unordered_set>
using namespace std;
// Function to find all interleaving of string `X` and `Y`
void findInterleavings(string result, string X, string Y, auto &collection)
{
// insert `result` into the set if the end of both strings is reached
if (!X.length() && !Y.length())
{
collection.insert(result);
return;
}
// if the string `X` is not empty, append its first character in the
// result and recur for the remaining substring
if (X.length()) {
findInterleavings(result + X[0], X.substr(1), Y, collection);
}
// if the string `Y` is not empty, append its first character in the
// result and recur for the remaining substring
if (Y.length()) {
findInterleavings(result + Y[0], X, Y.substr(1), collection);
}
}
int main()
{
string X = "ABC";
string Y = "ACB";
// use set to handle duplicates
unordered_set<string> collection;
findInterleavings("", X, Y, collection);
for (string s: collection) {
cout << s << endl;
}
return 0;
}
Output:
ACBABC
AABCBC
ACABCB
ABCACB
AACBBC
ABACCB
ACABBC
ABACBC
AACBCB
AABCCB
Isomorphic Strings
Given two strings, determine whether they are isomorphic. Two strings, X and Y, are called isomorphic if all occurrences of each character in X can be replaced with another character to get Y and vice-versa.
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
// Find if strings `X` and `Y` are Isomorphic or not
bool isIsomorphic(string X, string Y)
{
// if `X` and `Y` have different lengths, they cannot be isomorphic
if (X.length() != Y.length()) {
return false;
}
// use a map to store a mapping from characters of string `X` to string `Y`
unordered_map<char, char> map;
// use set to store a pool of already mapped characters
unordered_set<char> set;
for (int i = 0; i < X.length(); i++)
{
char x = X[i], y = Y[i];
// if `x` is seen before
if (map.find(x) != map.end())
{
// return false if the first occurrence of `x` is mapped to a
// different character
if (map[x] != y) {
return false;
}
}
// if `x` is seen for the first time (i.e., it isn't mapped yet)
else {
// return false if `y` is already mapped to some other char in `X`
if (set.find(y) != set.end()) {
return false;
}
// map `y` to `x` and mark it as mapped
map[x] = y;
set.insert(y);
}
}
return true;
}
int main()
{
string X = "ACAB";
string Y = "XCXY";
if (isIsomorphic(X, Y)) {
cout << X << " and " << Y << " are Isomorphic";
}
else {
cout << X << " and " << Y << " are not Isomorphic";
}
return 0;
}
Output:
ACAB and XCXY are Isomorphic
Find all words that follow the same order of characters as given pattern
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
// Function to print all words that follows the same order of
// characters as the given pattern
void patternMatch(vector<string> const &list, string pattern)
{
// `len` stores the length of the pattern
int len = pattern.length();
// check each word in the input list
for (string word: list)
{
// `map1` stores the mapping from word to the pattern
// `map2` stores the mapping from pattern to word
unordered_map<char, char> map1, map2;
// proceed only when the length of the pattern and word is the same
if (word.length() == len)
{
int i;
// process each character in both word and pattern
for (i = 0; i < len; i++)
{
// `w` stores the current character of the current word
char w = word[i];
// `p` stores the current character of the pattern
char p = pattern[i];
/* Check mapping from the current word to the given pattern */
// if `w` is seen for the first time, store its mapping
// to `p` in `map1`
if (map1.find(w) == map1.end()) {
map1[w] = p;
}
// if `w` is seen before, its mapped character should be `p`
else if (map1[w] != p) {
break;
}
/* Check mapping from the given pattern to the current word */
// if `p` is seen for the first time, store its mapping to
// `w` in `map2`
if (map2.find(p) == map2.end()) {
map2[p] = w;
}
// if `p` is seen before, its mapped character should be `w`
else if (map2[p] != w) {
break;
}
}
// if the current word matches the pattern, print it
if (i == len) {
cout << word << " ";
}
}
}
}
int main()
{
// list of words
vector<string> list =
{
"leet", "abcd", "loot", "geek", "cool", "for", "peer",
"dear", "seed", "meet", "noon", "otto", "mess", "loss"
};
// given pattern
string pattern = "moon";
patternMatch(list, pattern);
return 0;
}
Output:
leet loot geek cool peer seed meet
Given a string, find first k non-repeating characters in it by doing only a single traversal of it.
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
using namespace std;
// Function to find first `k` non-repeating character in
// the string by doing only a single traversal
void findFirstKNonRepeating(string str, int k)
{
// map to store character count and the index of its
// last occurrence in the string
unordered_map<char, pair<int, int>> map;
for (int i = 0; i < str.length(); i++)
{
map[str[i]].first++;
map[str[i]].second = i;
}
// create an empty min-heap
priority_queue<int, vector<int>, greater<int>> pq;
// traverse the map and push the index of all characters
// having the count of 1 into the min-heap
for (auto it: map)
{
int count = it.second.first;
int index = it.second.second;
if (count == 1) {
pq.push(index);
}
}
// pop the top `k` keys from the min-heap
while (k-- && !pq.empty())
{
// extract the minimum node from the min-heap
int min_index = pq.top();
pq.pop();
cout << str[min_index] << " ";
}
}
int main()
{
string str = "ABCDBAGHCHFAC";
int k = 3;
findFirstKNonRepeating(str, k);
return 0;
}
Output:
D G F
Given a text, find all occurrences of a given pattern in it.
#include <iostream>
using namespace std;
// Function to find all occurrences of a pattern of length `m`
// in the given text of length `n`
void find(string text, string pattern)
{
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++)
{
for (int j = 0; j < m; j++)
{
if (text[i + j] != pattern[j]) {
break;
}
if (j == m - 1) {
cout << "The pattern occurs with shift " << i << endl;
}
}
}
}
int main()
{
string text = "ABCABAABCABAC";
string pattern = "CAB";
find(text, pattern);
return 0;
}
Output:
The pattern occurs with shift 2
The pattern occurs with shift 8
Given a string, in-place remove all occurrences of AB and C from it.
#include <stdio.h>
// Function to remove all occurrences of `AB` and `C` from the string
void Remove(char* str)
{
// `i` maintains the position of the current char in the input string.
// `k` maintains the next free position in the output string.
int i = 0, k = 0;
// do till the end of the string is reached
while (str[i])
{
// if the current is `B` and previous (need not be adjacent) was `A`,
// increment `i` and decrement `k`
if (str[i] == 'B' && (k > 0 && str[k - 1] == 'A')) {
--k, ++i;
}
// if the current char is `C`, increment `i`
else if (str[i] == 'C') {
++i;
}
else {
// for any other character, increment both `i` and `k`
str[k++] = str[i++];
}
}
// null-terminate the string
str[k] = '\0';
}
int main()
{
char str[] = "ABCACBCAABB";
Remove(str);
printf("The string after removal removal of 'AB' and 'C' is '%s'", str);
return 0;
}
Output:
The string after removal of ‘AB’ and ‘C’ is ”
Run–length encoding (RLE) is a simple form of lossless data compression that runs on sequences with the same value occurring many consecutive times. It encodes the sequence to store only a single value and its count.
#include <iostream>
#include <string>
using namespace std;
// Perform Run–length encoding (RLE) data compression algorithm
// on string `str`
string encode(string str)
{
// stores output string
string encoding = "";
int count;
for (int i = 0; str[i]; i++)
{
// count occurrences of character at index `i`
count = 1;
while (str[i] == str[i + 1]) {
count++, i++;
}
// append current character and its count to the result
encoding += to_string(count) + str[i];
}
return encoding;
}
int main()
{
string str = "ABBCCCD";
cout << encode(str);
return 0;
}
Output:
1A2B3C1D
This post will discuss how to validate an IP address (IPv4) in C++. A valid IPv4 address must be in the form of xxx.xxx.xxx.xxx, where xxx is a number from 0-255.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// check if a given string is a numeric string or not
bool isNumber(const string &str)
{
// `std::find_first_not_of` searches the string for the first character
// that does not match any of the characters specified in its arguments
return !str.empty() &&
(str.find_first_not_of("[0123456789]") == std::string::npos);
}
// Function to split string `str` using a given delimiter
vector<string> split(const string &str, char delim)
{
auto i = 0;
vector<string> list;
auto pos = str.find(delim);
while (pos != string::npos)
{
list.push_back(str.substr(i, pos - i));
i = ++pos;
pos = str.find(delim, pos);
}
list.push_back(str.substr(i, str.length()));
return list;
}
// Function to validate an IP address
bool validateIP(string ip)
{ // split the string into tokens
vector<string> list = split(ip, '.');
// if the token size is not equal to four
if (list.size() != 4) {
return false;
}
// validate each token
for (string str: list)
{
// verify that the string is a number or not, and the numbers
// are in the valid range
if (!isNumber(str) || stoi(str) > 255 || stoi(str) < 0) {
return false;
}
}
return true;
}
// Validate an IP address in C++
int main()
{
string ip = "14.8.9.28";
// string ip = "100.xyz.1.15";
// string ip = "115.300.10.60";
if (validateIP(ip)) {
cout << "Valid IP Address" << endl;
}
else {
cout << "Invalid IP Address" << endl;
}
return 0;
}
Output:
Valid IP Address
Given a string and a positive number k, find the longest substring of the string containing k distinct characters. If k is more than the total number of distinct characters in the string, return the whole string.
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
// Define the character range
#define CHAR_RANGE 128
// Function to find the longest substring of a given string containing
// `k` distinct characters using a sliding window
string findLongestSubstring(string str, int k, int n)
{
// stores the longest substring boundaries
int end = 0, begin = 0;
// set to store distinct characters in a window
unordered_set<char> window;
// Count array `freq` stores the frequency of characters present in the
// current window. We can also use a map instead of a count array.
int freq[CHAR_RANGE] = { 0 };
// `[low…high]` maintains the sliding window boundaries
for (int low = 0, high = 0; high < n; high++)
{
window.insert(str[high]);
freq[str[high]]++;
// if the window size is more than `k`, remove characters from the left
while (window.size() > k)
{
// If the leftmost character's frequency becomes 0 after
// removing it in the window, remove it from the set as well
if (--freq[str[low]] == 0) {
window.erase(str[low]);
}
low++; // reduce window size
}
// update the maximum window size if necessary
if (end - begin < high - low)
{
end = high;
begin = low;
}
}
// return the longest substring found at `str[begin…end]`
return str.substr(begin, end - begin + 1);
}
int main()
{
string str = "abcbdbdbbdcdabd";
int k = 2;
int n = str.length();
cout << findLongestSubstring(str, k, n);
return 0;
}
Output:
bdbdbbd
Check if a string is a rotated palindrome or not
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// Recursive function to check if `str[low…high]` is a palindrome or not
bool isPalindrome(string str, int low, int high)
{
return (low >= high) || (str[low] == str[high] &&
isPalindrome(str, low + 1, high - 1));
}
// Function to check if a given string is a rotated palindrome or not
bool isRotatedPalindrome(string str)
{
// length of the given string
int n = str.length();
// check for all rotations of the given string if it
// is palindrome or not
for (int i = 0; i < n; i++)
{
// in-place rotate the string by 1 unit
rotate(str.begin(), str.begin() + 1, str.end());
// rotate(str.rbegin(), str.rbegin() + 1, str.rend());
// return true if the rotation is a palindrome
if (isPalindrome(str, 0, n - 1)) {
return true;
}
}
// return false if no rotation is a palindrome
return false;
}
int main()
{
// palindromic string
string str = "ABCDCBA";
// rotate it by 2 units
rotate(str.begin(), str.begin() + 2, str.end());
if (isRotatedPalindrome(str)) {
cout << "The string is a rotated palindrome";
}
else {
cout << "The string is not a rotated palindrome";
}
return 0;
}
Longest Palindromic Substring Problem
#include <iostream>
#include <string>
using namespace std;
// Expand in both directions of `low` and `high` to find
// maximum length palindrome
string expand(string str, int low, int high)
{ int len = str.length();
// run till `str[low.high]` is a palindrome
while (low >= 0 && high < len && (str[low] == str[high])) {
low--, high++; // Expand in both directions
}
// return palindromic substring
return str.substr(low + 1, high - low - 1);
}
// Function to find the longest palindromic substring in `O(n²)` time
// and `O(1)` space
string findLongestPalindromicSubstring(string str, int len)
{
// `max_str` stores the maximum length palindromic substring
// found so far
string max_str = "", curr_str;
// `max_length` stores the maximum length of palindromic
// substring found so far
int max_length = 0, curr_length;
// consider every character of the given string as a midpoint and expand
// in both directions to find maximum length palindrome
for (int i = 0; i < len; i++)
{
// find the longest odd length palindrome with `str[i]` as a midpoint
curr_str = expand(str, i, i);
curr_length = curr_str.length();
// update maximum length palindromic substring if odd length
// palindrome has a greater length
if (curr_length > max_length)
{
max_length = curr_length;
max_str = curr_str;
}
// Find the longest even length palindrome with `str[i]` and `str[i+1]`
// as midpoints. Note that an even length palindrome has two
// midpoints.
curr_str = expand(str, i, i + 1);
curr_length = curr_str.length();
// update maximum length palindromic substring if even length
// palindrome has a greater length
if (curr_length > max_length)
{
max_length = curr_length;
max_str = curr_str;
}
}
return max_str;
}
int main()
{
string str = "ABDCBCDBDCBBC";
cout << "The longest palindromic substring of " << str << " is " << findLongestPalindromicSubstring(str, str.length() - 1);
return 0;
}
Output:
The longest palindromic substring of ABDCBCDBDCBBC is BDCBCDB
Check if a repeated subsequence is present in a string or not
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// Recursive function to check if `str[low…high]` is a palindrome or not
bool isPalindrome(string str, int low, int high)
{
// base case
if (low >= high) {
return true;
}
return (str[low] == str[high]) &&
isPalindrome(str, low + 1, high - 1);
}
// Function to checks if repeated subsequence is present
// in the string
bool hasRepeatedSubsequence(string str)
{
// map to store the frequency of each distinct character
// of a given string
unordered_map<char, int> freq;
// update map with frequency
for (int i = 0; i < str.length(); i++)
{
// if the frequency of any character becomes 3,
// we have found the repeated subsequence
if (++freq[str[i]] >= 3) {
return true;
}
}
string temp;
// consider all repeated elements (frequency 2 or more)
// and discard all non-repeating elements (frequency 1)
for (int i = 0; i < str.length(); i++)
{
if (freq[str[i]] >= 2) {
temp += str[i];
}
}
// return false if `temp` is a palindrome
return !isPalindrome(temp, 0, temp.length() - 1);
}
int main()
{
string str = "XYBYAXB"; // `XB` and `YB` are repeated subsequences
if (hasRepeatedSubsequence(str)) {
cout << "Repeated subsequence is present";
}
else {
cout << "No repeated subsequence is present";
}
return 0;
}
Output:
Repeated subsequence is present
Check if strings can be derived from each other by circularly rotating them
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// Function to check if `X` can be derived from `Y` by rotating it
bool check(string X, string Y)
{
int m;
// if string lengths are different, they can't be
// derived from each other
if ((m = X.length()) != Y.length()) {
return false;
}
// Invariant: At the i'th iteration of this loop,
// the string `X` will be rotated by `i` units
for (int i = 0; i < m; i++)
{
// in-place left rotates string `X` by 1 unit
rotate(X.begin(), X.begin() + 1, X.end());
// for right rotation, we can use reverse iterators.
// i.e., rotate(X.rbegin(), X.rbegin() + 1, X.rend());
// return true if `X` becomes equal to `Y`
if (!X.compare(Y)) {
return true;
}
}
// return false if no rotation is matched
return false;
}
int main()
{
string X = "ABCD";
string Y = "DABC";
if (check(X, Y)) {
cout << "Given strings can be derived from each other";
}
else {
cout << "Given strings cannot be derived from each other";
}
return 0;
}
Output:
Given strings can be derived from each other
Convert a number into a corresponding excel column name
#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
// Function to convert a given number to an Excel column
string getColumnName(int n)
{
// initialize output string as empty
string result = "";
while (n > 0)
{
// find the index of the next letter and concatenate the letter
// to the solution
// here index 0 corresponds to `A`, and 25 corresponds to `Z`
int index = (n - 1) % 26;
result = char(index + 'A') + result;
n = (n - 1) / 26;
}
return result;
}
int main()
{
// seed for random input
srand(time(NULL));
// generate column names for 10 random numbers between 1–1000
for (int i = 1; i <= 10; i++)
{
int r = rand() % 1000 + 1;
cout << r << " — " << getColumnName(r) << endl;
}
return 0;
}
Output (will vary):
585 — VM
873 — AGO
269 — JI
849 — AFQ
288 — KB
962 — AJZ
549 — UC
572 — UZ
485 — RQ
704 — AAB
Determine whether two strings are anagram or not
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// Function to check if `X` and `Y` are anagrams or not
bool isAnagram(string X, string Y)
{
// if X's length is not the same as Y's, they can't be an anagram
if (X.length() != Y.length()) {
return false;
}
// create an empty map
unordered_map<int, int> freq;
// maintain a count of each character of `X` on the map
for (char x: X) {
freq[x]++;
}
// do for each character `y` of `Y`
for (char y: Y)
{
// if `y` is not found in the map, i.e., either `y` is not present
// in string `X` or has more occurrences in string `Y`
if (freq.find(y) == freq.end()) {
return false;
}
// decrease the frequency of `y` on the map
freq[y]--;
// if its frequency becomes 0, erase it from the map
if (!freq[y]) {
freq.erase(y);
}
}
// return true if the map becomes empty
return !freq.size();
}
int main()
{
string X = "tommarvoloriddle"; // Tom Marvolo Riddle
string Y = "iamlordvoldemort"; // I am Lord Voldemort
if (isAnagram(X, Y)) {
cout << "Anagram";
}
else {
cout << "Not an Anagram";
}
return 0;
}
Output:
Anagram
[ ] Wildcard
Given a binary pattern containing ? wildcard character at a few positions, find all possible combinations of binary strings that can be formed by replacing the wildcard character by either 0 or 1.
#include <iostream>
#include <stack>
using namespace std;
// Find all binary strings that can be formed from a given
// wildcard pattern
void printAllCombinations(string pattern)
{
// create an empty stack (we can also use set, queue, vector, or
// any other container)
stack<string> list;
list.push(pattern); // push the pattern into the stack
size_t index;
// loop till stack is empty
while (!list.empty())
{
// pop a string from the stack and process it
string curr = list.top();
list.pop();
// `index` stores position of the first occurrence of wildcard
// pattern in `curr`
if ((index = curr.find_first_of('?')) != string::npos)
{
for (int i = 0; i < 2; i++)
{
// replace `?` with 0 and 1 and push it into the stack
curr[index] = i + '0';
list.push(curr);
}
}
// if no wildcard pattern is found, print the string
else {
cout << curr << endl;
}
}
}
int main()
{
string str = "1?11?00?1?";
printAllCombinations(str);
return 0;
}
Output:
1111100111
1111100110
1111100011
1111100010
1111000111
1111000110
1111000011
1111000010
1011100111
1011100110
1011100011
1011100010
1011000111
1011000110
1011000011
1011000010
Find all interleaving of given strings
#include <iostream>
#include <unordered_set>
using namespace std;
// Function to find all interleaving of string `X` and `Y`
void findInterleavings(string result, string X, string Y, auto &collection)
{
// insert `result` into the set if the end of both strings is reached
if (!X.length() && !Y.length())
{
collection.insert(result);
return;
}
// if the string `X` is not empty, append its first character in the
// result and recur for the remaining substring
if (X.length()) {
findInterleavings(result + X[0], X.substr(1), Y, collection);
}
// if the string `Y` is not empty, append its first character in the
// result and recur for the remaining substring
if (Y.length()) {
findInterleavings(result + Y[0], X, Y.substr(1), collection);
}
}
int main()
{
string X = "ABC";
string Y = "ACB";
// use set to handle duplicates
unordered_set<string> collection;
findInterleavings("", X, Y, collection);
for (string s: collection) {
cout << s << endl;
}
return 0;
}
Output:
ACBABC
AABCBC
ACABCB
ABCACB
AACBBC
ABACCB
ACABBC
ABACBC
AACBCB
AABCCB
Isomorphic Strings
Given two strings, determine whether they are isomorphic. Two strings, X and Y, are called isomorphic if all occurrences of each character in X can be replaced with another character to get Y and vice-versa.
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
// Find if strings `X` and `Y` are Isomorphic or not
bool isIsomorphic(string X, string Y)
{
// if `X` and `Y` have different lengths, they cannot be isomorphic
if (X.length() != Y.length()) {
return false;
}
// use a map to store a mapping from characters of string `X` to string `Y`
unordered_map<char, char> map;
// use set to store a pool of already mapped characters
unordered_set<char> set;
for (int i = 0; i < X.length(); i++)
{
char x = X[i], y = Y[i];
// if `x` is seen before
if (map.find(x) != map.end())
{
// return false if the first occurrence of `x` is mapped to a
// different character
if (map[x] != y) {
return false;
}
}
// if `x` is seen for the first time (i.e., it isn't mapped yet)
else {
// return false if `y` is already mapped to some other char in `X`
if (set.find(y) != set.end()) {
return false;
}
// map `y` to `x` and mark it as mapped
map[x] = y;
set.insert(y);
}
}
return true;
}
int main()
{
string X = "ACAB";
string Y = "XCXY";
if (isIsomorphic(X, Y)) {
cout << X << " and " << Y << " are Isomorphic";
}
else {
cout << X << " and " << Y << " are not Isomorphic";
}
return 0;
}
Output:
ACAB and XCXY are Isomorphic
Find all words that follow the same order of characters as given pattern
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;
// Function to print all words that follows the same order of
// characters as the given pattern
void patternMatch(vector<string> const &list, string pattern)
{
// `len` stores the length of the pattern
int len = pattern.length();
// check each word in the input list
for (string word: list)
{
// `map1` stores the mapping from word to the pattern
// `map2` stores the mapping from pattern to word
unordered_map<char, char> map1, map2;
// proceed only when the length of the pattern and word is the same
if (word.length() == len)
{
int i;
// process each character in both word and pattern
for (i = 0; i < len; i++)
{
// `w` stores the current character of the current word
char w = word[i];
// `p` stores the current character of the pattern
char p = pattern[i];
/* Check mapping from the current word to the given pattern */
// if `w` is seen for the first time, store its mapping
// to `p` in `map1`
if (map1.find(w) == map1.end()) {
map1[w] = p;
}
// if `w` is seen before, its mapped character should be `p`
else if (map1[w] != p) {
break;
}
/* Check mapping from the given pattern to the current word */
// if `p` is seen for the first time, store its mapping to
// `w` in `map2`
if (map2.find(p) == map2.end()) {
map2[p] = w;
}
// if `p` is seen before, its mapped character should be `w`
else if (map2[p] != w) {
break;
}
}
// if the current word matches the pattern, print it
if (i == len) {
cout << word << " ";
}
}
}
}
int main()
{
// list of words
vector<string> list =
{
"leet", "abcd", "loot", "geek", "cool", "for", "peer",
"dear", "seed", "meet", "noon", "otto", "mess", "loss"
};
// given pattern
string pattern = "moon";
patternMatch(list, pattern);
return 0;
}
Output:
leet loot geek cool peer seed meet
Given a string, find first k non-repeating characters in it by doing only a single traversal of it.
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
using namespace std;
// Function to find first `k` non-repeating character in
// the string by doing only a single traversal
void findFirstKNonRepeating(string str, int k)
{
// map to store character count and the index of its
// last occurrence in the string
unordered_map<char, pair<int, int>> map;
for (int i = 0; i < str.length(); i++)
{
map[str[i]].first++;
map[str[i]].second = i;
}
// create an empty min-heap
priority_queue<int, vector<int>, greater<int>> pq;
// traverse the map and push the index of all characters
// having the count of 1 into the min-heap
for (auto it: map)
{
int count = it.second.first;
int index = it.second.second;
if (count == 1) {
pq.push(index);
}
}
// pop the top `k` keys from the min-heap
while (k-- && !pq.empty())
{
// extract the minimum node from the min-heap
int min_index = pq.top();
pq.pop();
cout << str[min_index] << " ";
}
}
int main()
{
string str = "ABCDBAGHCHFAC";
int k = 3;
findFirstKNonRepeating(str, k);
return 0;
}
Output:
D G F
Given a text, find all occurrences of a given pattern in it.
#include <iostream>
using namespace std;
// Function to find all occurrences of a pattern of length `m`
// in the given text of length `n`
void find(string text, string pattern)
{
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++)
{
for (int j = 0; j < m; j++)
{
if (text[i + j] != pattern[j]) {
break;
}
if (j == m - 1) {
cout << "The pattern occurs with shift " << i << endl;
}
}
}
}
int main()
{
string text = "ABCABAABCABAC";
string pattern = "CAB";
find(text, pattern);
return 0;
}
Output:
The pattern occurs with shift 2
The pattern occurs with shift 8
Given a string, in-place remove all occurrences of AB and C from it.
#include <stdio.h>
// Function to remove all occurrences of `AB` and `C` from the string
void Remove(char* str)
{
// `i` maintains the position of the current char in the input string.
// `k` maintains the next free position in the output string.
int i = 0, k = 0;
// do till the end of the string is reached
while (str[i])
{
// if the current is `B` and previous (need not be adjacent) was `A`,
// increment `i` and decrement `k`
if (str[i] == 'B' && (k > 0 && str[k - 1] == 'A')) {
--k, ++i;
}
// if the current char is `C`, increment `i`
else if (str[i] == 'C') {
++i;
}
else {
// for any other character, increment both `i` and `k`
str[k++] = str[i++];
}
}
// null-terminate the string
str[k] = '\0';
}
int main()
{
char str[] = "ABCACBCAABB";
Remove(str);
printf("The string after removal removal of 'AB' and 'C' is '%s'", str);
return 0;
}
Output:
The string after removal of ‘AB’ and ‘C’ is ”
Run–length encoding (RLE) is a simple form of lossless data compression that runs on sequences with the same value occurring many consecutive times. It encodes the sequence to store only a single value and its count.
#include <iostream>
#include <string>
using namespace std;
// Perform Run–length encoding (RLE) data compression algorithm
// on string `str`
string encode(string str)
{
// stores output string
string encoding = "";
int count;
for (int i = 0; str[i]; i++)
{
// count occurrences of character at index `i`
count = 1;
while (str[i] == str[i + 1]) {
count++, i++;
}
// append current character and its count to the result
encoding += to_string(count) + str[i];
}
return encoding;
}
int main()
{
string str = "ABBCCCD";
cout << encode(str);
return 0;
}
Output:
1A2B3C1D
This post will discuss how to validate an IP address (IPv4) in C++. A valid IPv4 address must be in the form of xxx.xxx.xxx.xxx, where xxx is a number from 0-255.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// check if a given string is a numeric string or not
bool isNumber(const string &str)
{
// `std::find_first_not_of` searches the string for the first character
// that does not match any of the characters specified in its arguments
return !str.empty() &&
(str.find_first_not_of("[0123456789]") == std::string::npos);
}
// Function to split string `str` using a given delimiter
vector<string> split(const string &str, char delim)
{
auto i = 0;
vector<string> list;
auto pos = str.find(delim);
while (pos != string::npos)
{
list.push_back(str.substr(i, pos - i));
i = ++pos;
pos = str.find(delim, pos);
}
list.push_back(str.substr(i, str.length()));
return list;
}
// Function to validate an IP address
bool validateIP(string ip)
{ // split the string into tokens
vector<string> list = split(ip, '.');
// if the token size is not equal to four
if (list.size() != 4) {
return false;
}
// validate each token
for (string str: list)
{
// verify that the string is a number or not, and the numbers
// are in the valid range
if (!isNumber(str) || stoi(str) > 255 || stoi(str) < 0) {
return false;
}
}
return true;
}
// Validate an IP address in C++
int main()
{
string ip = "14.8.9.28";
// string ip = "100.xyz.1.15";
// string ip = "115.300.10.60";
if (validateIP(ip)) {
cout << "Valid IP Address" << endl;
}
else {
cout << "Invalid IP Address" << endl;
}
return 0;
}
Output:
Valid IP Address
Given a string and a positive number k, find the longest substring of the string containing k distinct characters. If k is more than the total number of distinct characters in the string, return the whole string.
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
// Define the character range
#define CHAR_RANGE 128
// Function to find the longest substring of a given string containing
// `k` distinct characters using a sliding window
string findLongestSubstring(string str, int k, int n)
{
// stores the longest substring boundaries
int end = 0, begin = 0;
// set to store distinct characters in a window
unordered_set<char> window;
// Count array `freq` stores the frequency of characters present in the
// current window. We can also use a map instead of a count array.
int freq[CHAR_RANGE] = { 0 };
// `[low…high]` maintains the sliding window boundaries
for (int low = 0, high = 0; high < n; high++)
{
window.insert(str[high]);
freq[str[high]]++;
// if the window size is more than `k`, remove characters from the left
while (window.size() > k)
{
// If the leftmost character's frequency becomes 0 after
// removing it in the window, remove it from the set as well
if (--freq[str[low]] == 0) {
window.erase(str[low]);
}
low++; // reduce window size
}
// update the maximum window size if necessary
if (end - begin < high - low)
{
end = high;
begin = low;
}
}
// return the longest substring found at `str[begin…end]`
return str.substr(begin, end - begin + 1);
}
int main()
{
string str = "abcbdbdbbdcdabd";
int k = 2;
int n = str.length();
cout << findLongestSubstring(str, k, n);
return 0;
}
Output:
bdbdbbd
