Strings(Basic)

String - 1: Reverse a string

Link - https://leetcode.com/problems/reverse-string/description/

void reverseString(vector<char>& s) { cpp

int n = s.size();

int low = 0;
int high = n-1;

while(low<high){
swap(s[low++],s[high--]);
}
}

String - 2: Valid Palindrome

Link - https://leetcode.com/problems/valid-palindrome/
class Solution { cpp
public:
// functon to convert all Upper Case to Lower Case chars
char toLowerCase(char ch){
if(ch >= 'A' && ch <= 'Z'){
return ch - 'A' + 'a';
}
return ch;
}

//check if the character is alpahaNumeric or not(return true if it is else faLse)

bool checkValid(char ch){
return ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9';
}

bool isPalindrome(string s) {
int low = 0;
int high = s.length() - 1;

while(low <= high){

while(low < high && !checkValid(s[low])){
low++;
}
while(low < high && !checkValid(s[high])){
high--;
}
if(toLowerCase(s[low]) != toLowerCase(s[high])){
return false;
}
else{
 low++;
high--;
}
}
return true;
}
};

String - 3: Reverse words in a string

Link - https://leetcode.com/problems/reverse-words-in-a-string/description/

Note: Here we have extra spaces i.e. there can me more than one space between the
words

class Solution { cpp

public:
string reverseWords(string s) {
int i = 0;
int n = s.length();

string ans = "";

while (i < n) {
//Initialize a empty temporary string
string temp = "";
// if we counter spaces increase the i pointer
while (i < n && s[i] == ' ') {
i++;
}
// if we encounter characters
 while (i < n && s[i] != ' ') {
temp = temp + s[i];
i++;
}

// if temp is not empty

if (temp.size() > 0) {
if (ans.empty()) {
ans = temp;
}

else {
ans = temp + " " + ans;
}
}
}
return ans;
}
};

String - 4: Reverse words in a string-II

Link - https://www.naukri.com/code360/problems/reverse-the-order-of-words-in-a-
string_1264991?leftPanelTabValue=PROBLEM

Note: Here we have no extra spaces i.e. there is only one space between the words

#include<bits/stdc++.h> cpp

string reverseOrderWords(string str) {

int start = 0;

for(int i = 0; i <= str.length(); i++){

if(i == str.length() || str[i] == ' ') {
int end = i;
reverse(str.begin() + start, str.begin() + i);
 start = i + 1;
}
}

reverse(str.begin(),str.end());
return str;
}

String - 5: Maximum occurring character

Link - https://www.geeksforgeeks.org/problems/maximum-occuring-character-1587115620/1

Using a map:

char getMaxOccuringChar(string str) cpp

{
map<char,int> mpp;

for(auto& el : str){
mpp[el]++;
}

char cnt = 0;
char max = 'a';
for(auto& pair : mpp){
if(pair.second > cnt){
max = pair.first;
cnt = pair.second;
}
}
 return max;

Using Hashing: By mapping all the characters into numbers from 1 to 26 as there
are 26 alphabets

char getMaxOccuringChar(string str) cpp

{
int n = str.length();
int arr[26] ={0};

for(int i = 0; i <n;i++){
int number = 0;
number = str[i] -'a'; // mapping the characters into numbers

arr[number]++;

int maxi = -1; int ans = 0;

for(int i = 0 ; i < 26; i++){

if(arr[i] > maxi){
ans = i;
maxi = arr[i];
}
}

return ans + 'a'; //converting the number into character

String - 6:Replace Spaces

Link - https://bit.ly/4dfTuP8
 string replaceSpaces(string &str){ cpp
string temp = "";

for(int i = 0; i < str.size();i++){

if(str[i] == ' '){
temp.push_back('@');
temp.push_back('4');
temp.push_back('0');
}
else{
temp.push_back(str[i]);
}
}
return temp;
}

Using Delimiter:(https://www.geeksforgeeks.org/cpp-string-to-vector-using-
delimiter/)

#include <bits/stdc++.h> cpp

vector<string> split(string str, char delimiter)
{
// Using str in a string stream
stringstream ss(str);
vector<string> res;
string token;
while (getline(ss, token, delimiter)) {
res.push_back(token);
}
return res;
}
 string replaceSpaces(string &str){
vector<string> res = split(str, ' ');
string ans;
for (size_t i = 0; i < res.size(); i++) {
ans += res[i]; // Concatenate the tokens
if (i < res.size() - 1) {// condition ensures that @40 is not added after the last
ans += "@40"; // Add "@40" in place of spaces
}
}
return ans;
}

String - 7:Remove all occurrences of a substring

Link -https://leetcode.com/problems/remove-all-occurrences-of-a-substring/description/

string removeOccurrences(string s, string part) { cpp

while (s.length() != 0 && s.find(part) < s.length()) {

s.erase(s.find(part), part.length());
}
return s;
}

s.find(part) returns the starting index of the first occurrence of part in s.

If part is not found, s.find(part) returns string::npos, which is typically a
large number greater than the length of s. The condition s.find(part) <
s.length() ensures that part is actually found in s.
String - 8: Permutation in String
Link -https://leetcode.com/problems/permutation-in-string/description/

class Solution { cpp

public:
bool checkEqual(int a[26] ,int b[26] ){
for(int i = 0;i < 26; i++){
if(a[i] != b[i]) return 0;
}
return 1;
}
bool checkInclusion(string s1, string s2) {
int count1[26] = {0};
//character count array
for(int i = 0 ; i < s1.size(); i++){
int index = s1[i] - 'a';
count1[index]++;
}

//traverse s2 string in window of size s1 length and compare

int i = 0;
int windowSize = s1.length();
int count2[26] = {0};
//running for first window
while(i < windowSize && i < s2.length()){
int index = s2[i] - 'a';
count2[index]++;
i++;
}
 if(checkEqual(count1, count2)){
return 1;
}

//check next window

while(i < s2.length()){
char newChar = s2[i];
int index = newChar - 'a';
count2[index]++;

int oldChar = s2[i - windowSize];

index = oldChar - 'a';
count2[index]--;
i++;

if(checkEqual(count1, count2)) return 1;

}

return 0;

}
};

String - 9: Remove all adjacent duplicates in a string

Link -https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/description/
 string removeDuplicates(string s) { cpp
// int i = 0;
// while(s.length() > 0 && i < s.length() - 1){
// while(s[i] != s[i+1] && i < s.length() - 1){
// i++;
// }
// if(s[i] == s[i+1]){
// s.erase(i,2);
// i = 0;
// }
// }
// return s;
int i = 0;
while (i < s.length() - 1 && s.length() > 0) {
if (s[i] == s[i + 1])
{
s.erase(i, 2);
i = 0;
} else
{
i++;
}
}
return s;
}

String - 10: String Compression

Link -https://leetcode.com/problems/string-compression/description/
class Solution { cpp
public:
int compress(vector<char>& chars) {
int i = 0;
int ansIndex = 0;
int n = chars.size();

while(i < n){

int j = i + 1;

while(j < n && chars[i] == chars[j]){

j++;
}
//now j will point to the next different index
chars[ansIndex++] = chars[i];

int cnt = j - i;

if(cnt > 1){

//converting counting into a string
string str = to_string(cnt);

for(auto& ele : str){

chars[ansIndex++] = ele;
}
}
//Moving to different character
i = j;
}
return ansIndex;
}
};
String - 11. Remove outermost parenthesis

class Solution { cpp

public:
string removeOuterParentheses(string s) {
string res = "";
int cnt = 0;

for(char ch : s){
if(ch == '('){
// Add only if it is not the outermost '(' i.e if cnt == 0 it is the outer most parenthesis
if(cnt > 0){
res += ch;
}
cnt++;
}
if(ch == ')'){
cnt--;
// Add only if it is not the outermost ')' i.e if cnt == 0 it is the outer most parenthesis
if(cnt > 0){
res += ch;
}
}
}
return res;
}
};

String - 12. Largest odd number in a string

 class Solution { cpp
public:
string largestOddNumber(string num) {

for(int i = num.length() - 1; i >=0 ; i--){

if((num[i] - '0') % 2 == 1 ) return num.substr(0,i+1);
}
return "";
}
};

String - 13. Longest common prefix

 class Solution { cpp
public:
string longestCommonPrefix(vector<string>& strs) {
string s = ""; // Initialize the result string to store the common prefix

// Iterate through each character of the first string in the vector

for (int i = 0; i < strs[0].length(); i++) {
char temp = strs[0][i]; // Get the current character from the first string

// Compare this character with the corresponding character in all other strings
for (string& ele : strs) {

// If the character doesn't match or the index exceeds the length of any strin
g, return the result
if (temp != ele[i] || i >= ele.length()) return s;
}

// If all strings have the same character at this position, add it to the result
s.push_back(temp);
}

// Return the common prefix after checking all characters

return s;
}
};

String - 14. Isomorphic Strings

 class Solution { cpp
public:
bool isIsomorphic(string s, string t) {
map<char, char> mpp; // Map to store character mappings from s to t
set<char> ch; // Set to track characters already mapped in t

// Iterate through each character in s and t

for (int i = 0; i < s.length(); i++) {
if (mpp.find(s[i]) == mpp.end()) { // If s[i] is not yet mapped
if (ch.find(t[i]) != ch.end()) // If t[i] is already mapped, return false
return false;

mpp[s[i]] = t[i]; // Map s[i] to t[i]

ch.insert(t[i]); // Mark t[i] as used
}
}

// Verify the mappings are consistent across the strings

for (int i = 0; i < t.length(); i++) {
if (t[i] != mpp[s[i]]) // If mapping is inconsistent, return false
return false;
}

return true; // Return true if all mappings are valid and consistent
}
};

String - 15. Check whether one string is a rotation of

another
 class Solution { cpp
public:
bool rotateString(string s, string goal) {

int n = s.size(); // Get the length of string s

int m = goal.size(); // Get the length of string goal

// If the lengths are not equal, they can't be rotations of each other
if (n != m)
return false;

// Try rotating the string s n times

for (int i = 0; i < n; i++)
{
// Rotate the string by moving the first character to the end
s = s.substr(1) + s[0];

// If the rotated string matches the goal, return true

if (s == goal)
{
return true;
}
}

// If no rotation matches the goal, return false

return false;
}
};

String - 16. Valid anagram

 class Solution { cpp
public:
bool isAnagram(string s, string t) {
int n = s.size();
int m = t.size();

if(n != m) return false;

int count1[26] = {0};

int count2[26] = {0};

for(int i = 0; i < n; i++){

int index1 = s[i] -'a';
int index2 = t[i] -'a';

count1[index1]++;
count2[index2]++;
}

for(int i = 0; i < 26; i++){

if(count1[i] != count2[i]) return false;
}
return true;

}
};

String - 17. Sort characters by frequency

 class Solution { cpp
public:
string frequencySort(string s) {
map<char,int> freq;
for(int i = 0; i < s.size(); i++){
freq[s[i]]++;
}
sort(s.begin(),s.end(),[&](char a,char b){
if(freq[a] != freq[b]) return freq[a] > freq[b];
return a < b;
});

return s;
}
};

String - 18. Maximum Nesting Depth of the Parenthesis

 class Solution { cpp
public:
int maxDepth(string s) {

int cnt = 0;
int maxi = 0;

for(int i = 0; i < s.length(); i++){

if(s[i] == '('){
cnt++;
}
if(s[i] == ')'){
maxi = max(maxi,cnt);
cnt--;
}
}

return maxi;
}
};

String - 18. Roman Number to Integer

class Solution { cpp
public:
int value(char ch){
if(ch == 'I') return 1;
if(ch == 'V') return 5;
if(ch == 'X') return 10;
if(ch == 'L') return 50;
if(ch == 'C') return 100;
if(ch == 'D') return 500;
if(ch == 'M') return 1000;
return -1;
}
int romanToInt(string s) {
int result = 0;
 int n = s.length();
for(int i = 0; i < n; i++){
int s1 = value(s[i]);

if(i < n){

int s2 = value(s[i+1]);
if(s1 >= s2) result += s1;
else{
result += s2 - s1;
i++;
}
}
else result += s1;
}
return result;
}
};

String - 19. Implement Atoi

 class Solution { cpp
public:
int myAtoi(string s) {
int i = 0;
int n = s.size();

//if you encounter spaces

while(i < n && s[i] == ' ') i++;

//Store the sign

int sign = 1;
if(i < n && (s[i] == '-' || s[i] == '+')){
sign = (s[i] == '-')? -1 : 1;
i++;
}

long long ans = 0;

while(i < n && s[i] >= '0' && s[i] <= '9'){
long long temp = s[i] - '0';
ans = ans*10 + temp;
//check the current number
long long check = sign*ans;
if(check > INT_MAX) return INT_MAX;
if(check < INT_MIN) return INT_MIN;
i++;
}
return ans*sign;

}
};

String - 20. Count number of substrings

// Function to calculate the number of substrings with exactly 'k' distinct characters. cpp
long long int solve(string s, int k) {
long long ans = 0; // Stores the final count of substrings.
int cnt = 0; // Counts distinct characters in the current window.
int i = 0, j = 0; // Two pointers to represent the window's start (i) and end (j).
int size = s.size(); // Length of the input string.
vector<int> mp(26, 0); // Frequency map to count the occurrences of each character in the w
indow.

// Iterate over the string with the 'j' pointer.

while (j < size) {
mp[s[j] - 'a']++; // Increment the frequency of the current character.

if (mp[s[j] - 'a'] == 1) cnt++; // If it's the first occurrence of the character, incre
ase the distinct count.

// If the distinct count exceeds 'k', adjust the window by moving 'i'.
while (cnt > k) {
mp[s[i] - 'a']--; // Decrease the frequency of the character at 'i'.

if (mp[s[i] - 'a'] <= 0) { // If the character count becomes zero, reduce the disti
nct count.
cnt--;
}
i++; // Move the start of the window forward.
}

ans += j - i + 1; // Add the number of valid substrings ending at 'j' to the answer.
j++; // Move the end of the window forward.
 }

return ans; // Return the total number of substrings with at most 'k' distinct characters.
}

// Function to calculate the number of substrings with exactly 'k' distinct characters.
long long int substrCount(string s, int k) {
// Subtract the count of substrings with at most (k-1) distinct characters from the count o
f substrings with at most 'k' distinct characters.
return solve(s, k) - solve(s, k-1);
}

String - 21. Longest Palindromic substring

class Solution { cpp
public:
string longestPalindrome(string s) {
int start = 0;
int maxLen = 1;

int n = s.size();

for(int i = 1; i < n; i++){

//even length palindrome
int l = i - 1;
int r = i;

while(l >= 0 && r < n && s[l] == s[r]){

if(r - l + 1 > maxLen){
maxLen = r - l + 1;
start = l;
}
l--;
r++;
}

//odd length palindrome

l = i - 1;
r = i + 1;

while(l >= 0 && r < n && s[l] == s[r]){

if(r - l + 1 > maxLen){
maxLen = r - l + 1;
start = l;
}
l--;
r++;
}
 }
return s.substr(start,maxLen);

}
};

String - 22. Sum of Beauty of all Substrings

class Solution { cpp

public:
// Function to calculate the "beauty" of a given substring.
int sumOfBeauty(string s) {
int ch[26] = {0}; // Array to store the frequency of each character in the substring.

// Count the frequency of each character in the substring.

for (int i = 0; i < s.size(); i++) {
ch[s[i] - 'a']++;
}

int minFreq = INT_MAX; // Variable to track the minimum frequency of characters in the
substring.
int maxFreq = 0; // Variable to track the maximum frequency of characters in the
substring.

// Find the minimum and maximum frequency among the characters.

for (int i = 0; i < 26; i++) {
if (ch[i] > 0) { // Only consider characters that appear in the substring.
minFreq = min(ch[i], minFreq);
maxFreq = max(ch[i], maxFreq);
 }
}

return maxFreq - minFreq; // Return the difference between max and min frequencies (bea
uty of the substring).
}

// Function to calculate the total beauty sum of all substrings in the string.
int beautySum(string s) {
int n = s.size(); // Length of the input string.
int ans = 0; // Variable to store the total beauty sum.

// Iterate over all possible substrings.

for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int sum = sumOfBeauty(s.substr(i, j - i + 1)); // Calculate the beauty of the c
urrent substring.
ans = ans + sum; // Add the beauty of the current substring to the total.
}
}

return ans; // Return the total beauty sum of all substrings.

}
};