Strings¶
Strings are sequences of characters used to represent text. Many algorithmic problems involve pattern matching, substring processing, hashing, and manipulation of characters.
1. Easy¶
/*
Question:
Given a valid parentheses string `s`, remove the outermost parentheses of every primitive string in the primitive decomposition of `s`.
Approach:
- We can iterate through the characters of the string and keep track of the number of open parentheses encountered.
- Whenever we encounter an opening parenthesis, if the count of open parentheses is greater than 0, we append it to the result string.
- When we encounter a closing parenthesis, we decrement the count of open parentheses and append it to the result string only if the count is greater than 1.
Code:
*/
string removeOuterParentheses(string s) {
string res;
int opened = 0;
for (auto c : s) {
if (c == '(') {
if (opened > 0)
res += c;
opened++;
} else {
if (opened > 1)
res += c;
opened--;
}
}
return res;
}
/*
Time Complexity: O(N), where N is the length of the input string `s`.
Space Complexity: O(N), where N is the length of the input string `s`.
*/
/*
Question:
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Example:
Input: s = "the sky is blue"
Output: "blue is sky the"
Approach:
- Initialize an empty string 'ans' to store the reversed words.
- Initialize 'start' and 'end' variables to keep track of the start and end indices of each word.
- Iterate through the input string 's'.
- Ignore leading spaces by advancing the iterator 'i' until a non-space character is found.
- Set 'start' to the current index 'i'.
- Find the end index 'end' of the current word by advancing 'i' until a space or the end of the string is encountered.
- Extract the current word using the substr() function and store it in a temporary string 'temp'.
- Reverse the characters in 'temp'.
- Append 'temp' to 'ans' with a space delimiter.
- Reverse the characters in 'ans' to get the reversed order of words.
- Remove any leading or trailing spaces in 'ans'.
- Return the resulting string 'ans'.
Code:
*/
string reverseWords(string s) {
string ans = "";
int start = -1, end = -1;
for(int i=0; i<s.size(); i++){
while(s[i]==' ')
i++;
start = i;
while(i<s.size() && s[i]!=' ')
i++;
end = i;
string temp = s.substr(start,end-start);
reverse(temp.begin(),temp.end());
ans = ans+" "+temp;
}
reverse(ans.begin(),ans.end());
int i=0, j=ans.size()-1;
while(ans[i]==' ')
i++;
while(ans[j]==' ')
j--;
ans = ans.substr(i,j-i+1);
return ans;
}
/*
Time Complexity: O(n), where n is the length of the input string 's'.
Space Complexity: O(n), where n is the length of the input string 's'.
*/
/*
Question:
You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.
A substring is a contiguous sequence of characters within a string.
Approach:
1. Iterate through the string from the last character.
2. Check if the current character is odd.
3. If it is odd, return the substring from the beginning of the string to the current character index.
4. If no odd number is found, return an empty string.
Time Complexity: O(N), where N is the length of the input string num.
- We iterate through the string once to find the largest odd number.
Space Complexity: O(1)
- We use constant space to store the result and iterate through the string.
Code:
*/
string largestOddNumber(string num) {
// Check the first odd number from last
for (int i = num.size() - 1; i >= 0; i--) {
if ((num[i] - '0') % 2 != 0)
return num.substr(0, i + 1);
}
return "";
}
/*
Question:
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Approach:
1. Sort the array of strings lexicographically.
2. Take the first and last string from the sorted array.
3. Compare each character of the first and last string until they don't match or the end of either string is reached.
4. Return the common prefix.
Time Complexity: O(N*M*log(N)), where N is the number of strings and M is the maximum length of the strings.
- Sorting the array of strings takes O(N*log(N)) time.
- Comparing the first and last string takes O(M) time.
Space Complexity: O(1)
- We use constant space.
Code:
*/
using namespace std;
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty())
return "";
sort(strs.begin(), strs.end());
int first = 0, last = strs.size() - 1;
int i = 0, j = 0;
int len = 0;
while (i < strs[first].size() && j < strs[last].size() && strs[first][len] == strs[last][len]) {
i++;
j++;
len++;
}
return strs[first].substr(0, len);
}
/*
Question:
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters.
No two characters may map to the same character, but a character may map to itself.
Approach:
1. Initialize two maps to store the mapping of characters from s to t and from t to s.
2. Iterate through each character in s and t simultaneously.
3. If the current characters in s and t are already mapped differently, return false.
4. If the current characters in s and t are not mapped yet, add them to the maps.
5. If the current characters in s and t are already mapped to each other, continue to the next characters.
6. If all characters have been iterated and no inconsistencies are found, return true.
Code:
*/
bool isIsomorphic(string s, string t) {
unordered_map<char, char> mps;
unordered_map<char, char> mpt;
for (int i = 0; i < s.size(); i++) {
if (mps.find(s[i]) == mps.end() && mpt.find(t[i]) == mpt.end()) {
mps[s[i]] = t[i];
mpt[t[i]] = s[i];
} else if (mps[s[i]] != t[i] || mpt[t[i]] != s[i]) {
return false;
}
}
return true;
}
/*
Time Complexity: O(n), where n is the length of the input strings s and t.
- We iterate through each character of s and t once.
Space Complexity: O(m), where m is the number of unique characters in the input strings s and t.
- In the worst case, all characters in s and t are unique, and we need to store mappings for all of them.
- The space complexity can also be considered as O(1) since the maximum number of unique characters is limited (26 English alphabets).
*/
/*
QUESTION: Rotate String
Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.
A shift on s consists of moving the leftmost character of s to the rightmost position.
Example:
Input: s = "abcde", goal = "cdeab"
Output: true
Input: s = "abcde", goal = "abced"
Output: false
Approach:
- First, we check if the lengths of the two strings `s` and `goal` are equal. If not, they cannot be rotated versions of each other, so we return `false`.
- Then, we concatenate `s` with itself to create a new string `concat`.
- We check if `goal` is a substring of `concat`. If it is, that means `s` can be transformed into `goal` by performing some number of left shifts, so we return `true`. Otherwise, we return `false`.
CODE:-
*/
bool rotateString(string s, string goal) {
if (s.size() != goal.size())
return false;
if ((s + s).find(goal) == string::npos)
return false;
return true;
}
/*
Time Complexity: The time complexity of this approach is O(N^2), where N is the length of the input strings `s` and `goal`. This is because the `find` function is used to search for the substring `goal` within the concatenated string, which has a time complexity of O(N^2).
Space Complexity: The space complexity is O(N), where N is the length of the input string `s`. This is because we create a new string `concat` by concatenating `s` with itself.
*/
/*
QUESTION:-
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Problem: Valid Anagram
Approach:
1. Create an unordered map to store the count of each character in string `s`.
2. Iterate over each character in `s` and increment its count in the map.
3. Iterate over each character in `t`.
- If the character is not present in the map or its count is zero, return false.
- Decrement the count of the character in the map.
- If the count becomes zero, remove the character from the map.
4. After iterating through all characters in `t`, if the map is empty, return true; otherwise, return false.
Code:
*/
bool isAnagram(string s, string t) {
unordered_map<char,int>mp;
for(auto c:s)
mp[c]++;
for(auto c:t){
if(mp.find(c)==mp.end())
return false;
mp[c]--;
if(mp[c]==0)
mp.erase(c);
}
return (mp.size()==0);
}
/*
Time complexity: O(max(s.length(), t.length()))
Space complexity: O(s.length())
*/
2. Medium¶
/*
Question:
Given a string s, sort it in decreasing order based on the frequency of the characters.
The frequency of a character is the number of times it appears in the string.
Approach:
1. Create a frequency map to count the occurrences of each character in the string.
2. Use a priority queue to sort the characters based on their frequencies in decreasing order.
3. Iterate through the priority queue and append the characters to a new string according to their frequencies.
Code:
*/
string frequencySort(string s) {
unordered_map<char, int> mp;
for (auto c : s) {
mp[c]++;
}
priority_queue<pair<int, char>> pq;
for (auto it : mp) {
pq.push({ it.second, it.first });
}
string ans = "";
while (!pq.empty()) {
auto curr = pq.top();
pq.pop();
ans.append(curr.first, curr.second);
}
return ans;
}
/*
Time Complexity: O(n log n), where n is the length of the string. Building the frequency map takes O(n) time, and the priority queue operations take O(n log n) time.
Space Complexity: O(n), where n is the length of the string. The space is used to store the frequency map and the priority queue.
*/
/*
Question:
Given a VPS represented as a string s, return the nesting depth of s.
Approach:
1. Initialize `opened` as 0 and `ans` as 0 to keep track of the number of opened parentheses and the maximum nesting depth respectively.
2. Iterate through each character `c` in the string `s`.
a. If `c` is an opening parenthesis '(', increment `opened` by 1 and update `ans` if it is greater than the current value of `ans`.
b. If `c` is a closing parenthesis ')', decrement `opened` by 1.
3. Return `ans` as the maximum nesting depth.
CODE:-
*/
int maxDepth(string s) {
int opened = 0, ans = 0;
for (auto c : s) {
if (c == '(') {
opened++;
ans = max(ans, opened);
} else if (c == ')') {
opened--;
}
}
return ans;
}
/*
Time Complexity: O(n), where n is the length of the string `s`.
Space Complexity: O(1)
*/
/*
Question:
Given a Roman numeral as a string, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Approach:
1. Create a map to store the values of each Roman symbol.
2. Initialize `result` as the value of the first symbol in the input string.
3. Iterate through each character `c` in the input string `s`, starting from the second character.
a. If the value of the current symbol is greater than the value of the previous symbol, subtract twice the value of the previous symbol from `result` and add the value of the current symbol.
b. Otherwise, add the value of the current symbol to `result`.
4. Return `result` as the converted integer.
Time Complexity: O(n), where n is the length of the input string `s`.
Space Complexity: O(1)
*/
int romanToInt(string s) {
unordered_map<char, int> symbolValues = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000}
};
int result = symbolValues[s[0]];
for (int i = 1; i < s.size(); i++) {
if (symbolValues[s[i]] > symbolValues[s[i - 1]]) {
result -= 2 * symbolValues[s[i - 1]];
result += symbolValues[s[i]];
} else {
result += symbolValues[s[i]];
}
}
return result;
}
/*
QUESTION:-
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).
The algorithm for myAtoi(string s) is as follows:
Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
Return the integer as the final result.
Note:
Only the space character ' ' is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
Example 1:
Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
The parsed integer is 42.
Since 42 is in the range [-231, 231 - 1], the final result is 42.
Example 2:
Input: s = " -42"
Output: -42
Explanation:
Step 1: " -42" (leading whitespace is read and ignored)
^
Step 2: " -42" ('-' is read, so the result should be negative)
^
Step 3: " -42" ("42" is read in)
^
The parsed integer is -42.
Since -42 is in the range [-231, 231 - 1], the final result is -42.
Approach:
1. Initialize an index `i` to track the current position in the string.
2. Skip any leading whitespace by incrementing `i` until a non-whitespace character is encountered.
3. Check if the next character (if not at the end of the string) is `'-'` or `'+'`. Set a `sign` flag accordingly to determine the final result's sign.
4. Read the consecutive digits until a non-digit character is encountered or the end of the input is reached. Convert these digits into an integer.
5. Apply the sign to the integer obtained from the digits.
6. If the integer is out of the 32-bit signed integer range, clamp it to the range [-231, 231 - 1].
7. Return the final integer.
Code:*/
int myAtoi(string s) {
int i = 0;
while (i < s.size() && s[i] == ' ')
i++;
if (i == s.size())
return 0;
bool sign = true; // indicates the number is positive
if (s[i] == '-') {
i++;
sign = false;
} else if (s[i] == '+')
i++;
long long ans = 0;
while (i < s.size() && (0 <= s[i] - '0' && s[i] - '0' <= 9)) {
long long digit = s[i] - '0';
ans = (ans * 10) + digit;
// handle overflow case
if (ans > INT_MAX && sign)
return INT_MAX;
else if (ans > INT_MAX)
return INT_MIN;
i++;
}
ans = sign ? ans : -1 * ans;
return (int) ans;
}
/*
- Time Complexity: The function scans the input string once, resulting in a linear time complexity of O(n), where n is the length of the input string.
- Space Complexity: The function uses a constant amount of extra space, resulting in constant space complexity, O(1).
*/
/*Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that have exactly k distinct characters.
Example 1:
Input:
S = "aba", K = 2
Output:
3
Explanation:
The substrings are:
"ab", "ba" and "aba".
Example 2:
Input:
S = "abaaca", K = 1
Output:
7
Explanation:
The substrings are:
"a", "b", "a", "aa", "a", "c", "a".
Approach:
1. We can solve this problem using the sliding window technique.
2. Initialize a variable ans to keep track of the count of substrings with exactly k distinct characters.
3. Create an unordered_map mp to store the count of characters in the current window.
4. Initialize two pointers i and j to mark the start and end of the window, both initially pointing to the start of the string.
5. Iterate j from the start to the end of the string:
- Increment the count of the current character s[j] in mp.
- If the number of distinct characters in mp exceeds k, move the start pointer i towards the right until the number of distinct characters becomes k again.
- Update the ans by adding the length of the current window (j - i + 1) to it.
6. Return the value of ans.
Code:*/
long long int substrAtmostK(string s, int k) {
long long int ans = 0;
unordered_map<char, int> mp;
int i = 0;
for (int j = 0; j < s.size(); j++) {
mp[s[j]]++;
while (mp.size() > k) {
mp[s[i]]--;
if (mp[s[i]] == 0)
mp.erase(s[i]);
i++;
}
ans += j - i + 1;
}
return ans;
}
long long int substrCount(string s, int k) {
long long int atmostk = substrAtmostK(s, k);
long long int atmostk_1 = substrAtmostK(s, k - 1);
return atmostk - atmostk_1;
}
/*Time Complexity: O(N), where N is the length of the input string.
Space Complexity: O(K), where K is the number of distinct characters.*/
/*
Question:-
Given a string `s`, the task is to find the longest palindromic substring in `s`.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Approach:
1. We define a helper function `expandFromCenter` that takes a string `s`, and two indices `start` and `end` as input.
2. The function expands from the center and checks if the substring from `start` to `end` is a palindrome.
3. If the length of the current palindrome is greater than the maximum length seen so far (`maxLen`), we update the maximum length and the corresponding start and end indices (`ans_start` and `ans_end`).
4. We iterate over each character of the string `s` and consider it as a potential center for the palindrome.
5. We call `expandFromCenter` twice for each character - once for considering odd-length palindromes and once for even-length palindromes.
6. Finally, we return the substring of `s` that corresponds to the longest palindromic substring.
Code:*/
void expandFromCenter(string s, int start, int end, int& ans_start, int& ans_end, int& maxLen) {
while (start >= 0 && end < s.size() && s[start] == s[end]) {
if (end - start + 1 > maxLen) {
ans_start = start;
ans_end = end;
maxLen = end - start + 1;
}
start--;
end++;
}
}
string longestPalindrome(string s) {
string ans = "";
int maxLen = 0, ans_start = -1, ans_end = -1;
for (int i = 0; i < s.size(); i++) {
// For odd length palindromes
expandFromCenter(s, i, i, ans_start, ans_end, maxLen);
// For even length palindromes
expandFromCenter(s, i - 1, i, ans_start, ans_end, maxLen);
}
return (maxLen == 0) ? "" : s.substr(ans_start, ans_end - ans_start + 1);
}
/*
Time Complexity: O(n^2), where n is the length of the input string `s`. The nested loops iterate over all possible pairs of indices.
Space Complexity: O(1), as we are using a constant amount of extra space.
*/
/*Question:
The beauty of a string is the difference in frequencies between the most frequent and least frequent characters.
Given a string `s`, you need to calculate the sum of beauty for all of its substrings. The beauty of a substring is defined as the difference between the highest and lowest frequency of any character in the substring.
Write a function `beautySum` that takes a string `s` as input and returns the sum of beauty for all substrings.
Example:
Input: s = "aabcb"
Output: 5
Explanation: The substrings with non-zero beauty are ["aab","aabc","aabcb","abcb","bcb"], each with beauty equal to 1.
Input: s = "aabcbaa"
Output: 17
Approach:
1. Initialize a variable `ans` to store the total beauty sum.
2. Iterate over the string `s` with the first loop, starting from index `i`.
- Initialize a frequency array `freq` of size 26, initialized with zeros.
- Iterate over the string `s` with the second loop, starting from index `j` equal to `i`.
- Increment the frequency of the character `s[j]` in the `freq` array.
- Calculate the difference between the highest and lowest frequencies in the `freq` array and add it to `ans`.
3. Return the value of `ans` as the final result.
CODE:-
*/
int get_maxmin(vector<int>& freq){
int maxi = INT_MIN, mini = INT_MAX;
for(auto it:freq){
maxi = max(maxi,it);
if(it!=0)
mini = min(mini,it);
}
return (mini==INT_MAX)?0:maxi-mini;
}
int beautySum(string s) {
int ans = 0;
// 2 loops to generate all substrings
for(int i=0; i<s.size(); i++){
vector<int>freq(26,0);
for(int j=i; j<s.size(); j++){
freq[s[j]-'a']++;
int maxmin = get_maxmin(freq);
ans += maxmin;
}
}
return ans;
}
/*
Time complexity :- for generating all substrings is O(n^2), where n is the length of the string `s`. For each substring, we calculate the difference between the highest and lowest frequencies, which takes O(26) or O(1) time since there are 26 lowercase alphabets. Therefore, the overall time complexity is O(n^2).
Space complexity :- O(26) or O(1) since we use a constant-sized frequency array to store the counts of characters.
*/