------ count no of valleys------------
int countingValleys(int steps, string path) {
int count=0;
int sum=0;
unordered_map<char,int>mpp={{'D',-1},{'U',1}};
for(int i=0;i<path.size();i++){
if(sum==0 && sum+mpp[path[i]]<0){
count++;
}
sum+=mpp[path[i]];
}
return count;
}
---------capital last and first of each word--------
void capital(string &s1){
for(int i=0;i<s1.size();i++){
if(s1[i]>='a' && s1[i]<'z'){
if(i==0 || i==s1.size()-1){
s1[i]=s1[i]-32;
}else if(s1[i+1]==' ' || s1[i-1]==' '){
s1[i]=s1[i]-32;
}
}
}
}
int main() {
// Write C++ code here
string input1;
getline(cin,input1);
capital(input1);
cout<<input1;
return 0;
}
----------largest and smallest word---------
#include <bits/stdc++.h>
using namespace std;
void capital(string &s1, string &maxword, string &minword) {
vector<string> ans;
string temp = "";
// Splitting words while handling multiple spaces
for (int i = 0; i < s1.size(); i++) {
if (s1[i] == ' ') {
if (!temp.empty()) { // Avoid empty words
ans.push_back(temp);
temp = "";
}
} else {
temp += s1[i];
}
}
if (!temp.empty()) { // Add the last word
ans.push_back(temp);
}
// If no words are found, return
if (ans.empty()) {
cout << "No words found in the input.\n";
return;
}
// Initialize min and max lengths properly
int max_length = 0;
int minlength = INT_MAX;
for (int i = 0; i < ans.size(); i++) {
if (ans[i].size() > max_length) {
max_length = ans[i].size();
maxword = ans[i];
cout << "Updated max_length: " << max_length << " (Word: " << maxword
<< ")\n";
}
if (ans[i].size() < minlength) {
minlength = ans[i].size();
minword = ans[i];
cout << "Updated minlength: " << minlength << " (Word: " << minword <<
")\n";
}
}
}
--------remove dots and reverse the words---------------
string reverse(string s1) {
s1.erase(0, s1.find_first_not_of('.'));
s1.erase(s1.find_last_not_of('.') + 1);
vector<string>ans;
string temp="";
for(int i=0;i<s1.size();i++){
if(s1[i]=='.'){
if(temp.size()!=0){
ans.push_back(temp);
temp="";
}
}else{
temp+=s1[i];
}
}
if(temp.size()!=0){
ans.push_back(temp);
}
reverse(ans.begin(),ans.end());
temp="";
for(int i=0;i<ans.size()-1;i++){
temp+=ans[i]+".";
}
temp+=ans[ans.size()-1];
return temp;
Examples:
Input: str = “i.like.this.program.very.much”
Output: str = “much.very.program.this.like.i”
Explanation:The words in the input string are reversed while maintaining the dots
as separators, resulting in "much.very.program.this.like.i".
Input: str = ”..geeks..for.geeks.”
Output: str = “geeks.for.geeks”
Input: str = “…home……”
Output: str = “home”
-------first occurence--------
int firstOccurence(string &txt, string &pat) {
// Your code here
return txt.indexOf(pat);
-----------lexicographically----------
If string is empty, we return ‘a’. If string contains all characters as ‘z’, we
append ‘a’ at the end. Otherwise we find first character from end which is not z
and increment it.
Input : raavz
Output : raawz
Since we can't increase last character,
we increment previous character.
Input : zzz
Output : zzza
string lexicography(string s1) {
bool done=false;
for(int i=s1.size()-1;i>=0;i--){
if(s1[i]=='z'){
continue;
}else{
s1[i]=s1[i]+1;
done=true;
break;
}
}
if(!done){
s1+='a';
}
return s1;
}
-------------Remove brackets from an algebraic string containing + and –
operators------------
Input : "(a-(b+c)+d)"
Output : "a-b-c+d"
#include <bits/stdc++.h>
using namespace std;
string simplify(string s) {
stack<int> st; // Stack to store signs
st.push(1); // Initial sign is '+'
string result = "";
int i = 0;
while (i < s.length()) {
if (s[i] == '+') {
// Use the current sign
if (st.top() == 1) {
result += '+';
} else {
result += '-';
}
i++;
} else if (s[i] == '-') {
// Flip the current sign
if (st.top() == 1) {
result += '-';
} else {
result += '+';
}
i++;
} else if (s[i] == '(') {
// Push the current sign onto the stack
if (i > 0 && s[i - 1] == '-') {
st.push(-st.top()); // Flip the sign for nested parentheses
} else {
st.push(st.top()); // Keep the same sign
}
i++;
} else if (s[i] == ')') {
// Pop the sign from the stack
st.pop();
i++;
} else {
// Append the character to the result
result += s[i];
i++;
}
}
return result;
}
-----------Remove Outermost Parentheses-----------
Input: s = "(()())(())"
Output: "()()()"
Explanation:
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
string removeOuterParentheses(string s) {
int counter=0;
//+1->opening bracket
//-1-->closing bracket
string result="";
for(int i=0;i<s.size();i++){
if(s[i]=='(' && counter!=0){
result+=s[i];
counter++;
}else if(s[i]==')' && counter-1!=0){
result+=s[i];
counter--;
}else if(s[i]=='(' && counter==0){
counter++;
}else{
counter--;
}
}
return result;
}
------------------largest odd number---------------------
Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.
string largestOddNumber(string num) {
int odd_idx=-1;
for(int i=num.size()-1;i>=0;i--){
if((num[i]-'0')%2!=0){
odd_idx=i;
break;
}
}
if(odd_idx!=-1){
return num.substr(0,odd_idx+1);
}
return "";
}
------------------common prefix----------------------------
string commonprefix(vector<string>&nums) {
string ans="";
sort(nums.begin(),nums.end());
int n=nums.size();
string low=nums[0];
string high=nums[n-1];
for(int i=0;i<low.size();i++){
if(low[i]!=high[i]){
break;
}
ans+=low[i];
}
return ans;
}
-------------------isomprphic string -------------------------
using one map
bool isIsomorphic(string s, string t) {
unordered_map<char, int> m1;
if(s.size()!=t.size())return false;
for(int i=0;i<s.size();i++){
if(m1.find(s[i])==m1.end()){
for (auto& pair : m1) {
if (pair.second == t[i]) {
return false;
}
}
m1[s[i]]=t[i];
}else if(m1.find(s[i])!=m1.end()){
if(t[i]!=m1[s[i]]){
return false;
}else{
continue;
}
}
}
return true;
}
using two maps
bool isIsomorphic(string s, string t) {
map<char,char>m1,m2;
for(int i=0;i<s.size();i++){
if(m1[s[i]]&& m1[s[i]]!=t[i])return false;
if(m2[t[i]]&& m2[t[i]]!=s[i])return false;
m1[s[i]]=t[i];
m2[t[i]]=s[i];
}
return true;
}
---------------------Rotate string of each other------------------
Input: s = "abcde", goal = "cdeab"
Output: true
public boolean rotateString(String s, String goal) {
if (s.length() != goal.length()) {
return false;
}
return (s + s).contains(goal);
}
--------------------Valid Anagram--------------------------------
there frequency will be the same
bool isAnagram(string s, string t) {
if(s.size()!=t.size())return false;
unordered_map<char,int>mpp;
for(int i=0;i<s.size();i++){
mpp[s[i]]++;
mpp[t[i]]--;
}
for(auto & it:mpp){
if(it.second>0){
return false;
}
}
return true;
}
--------------------sort by frequency---------------------
using map
static bool cmp(pair<char,int>&a,pair<char,int>&b){
if(a.second>b.second)return true;
else if(a.second==b.second){
return a.first<b.first;
}
return false;
}
string frequencySort(string s) {
map<char,int>mpp;
for(int i=0;i<s.size();i++){
mpp[s[i]]++;
}
vector<pair<char, int>> v;
for (auto &it : mpp) {
v.push_back({it.first, it.second});
}
sort(v.begin(),v.end(),cmp);
string c;
for (int i = 0; i < v.size(); i++) {
while (v[i].second--) {
c.push_back(v[i].first);
}
}
return c;
}
};
another approach
count array int count[256]={0}
-----------------------------Maximum Nesting Depth of the
Parentheses---------------------------
Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
class Solution {
public:
int maxDepth(string s) {
int maxi=0;
int counter=0;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
counter++;
maxi=max(maxi,counter);
}else{
counter--;
}
}
return maxi;
}
};
----------------------------integer to roman--------------------------
string intToRoman(int num) {
vector<pair<int, string>> values = {
{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
{100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
{10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}
};
string result = "";
for (auto& it : values) {
int value = it.first;
string symbol = it.second;
while (num >= value) {
result += symbol;
num -= value;
}
}
return result;
------------------------roman to integer--------------------------------
int romanToInt(string s) {
int ans=0;
unordered_map <char,int> mp{
{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
for(int i=0;i<s.size();i++){
if(mp[s[i]]<mp[s[i+1]]){
//for cases such as IV,CM, XL, etc...
ans=ans-mp[s[i]];
}
else{
ans=ans+mp[s[i]];
}
}
return ans;
}
------------------string to integer---------------------------------
class Solution {
public:
int myAtoi(string s) {
int n=s.size();
int i=0;
//remove leading zeros
while (i < n && s[i] == ' ') {
i++;
}
//check the sign
int sign=1;
if (s[i] == '-') { sign = -1; i++; }
else if (s[i] == '+') i++;
long res=0;
while(i<s.size() && isdigit(s[i])){
res=res*10+(s[i]-'0');
if(sign*res>INT_MAX)return INT_MAX;
if(sign*res<INT_MIN)return INT_MIN;
i++;
}
return (int)(sign*res);
}
};
---------------------------longest pallindrome substr-----------------------
string longestPalindrome(string s) {
//INTUTION::
// from any point move low poiter leftwise and right pointer rightwise and
check equal or not
string ans = "";
for (int i = 0; i < s.size(); i++) {
// Odd length
int low = i;
int high = i;
while (low >= 0 && high < s.size() && s[low] == s[high]) {
low--;
high++;
}
string palindromeOdd = s.substr(low + 1, high - low - 1);
if (palindromeOdd.size() > ans.size()) {
ans = palindromeOdd;
}
// Even length
low = i;
high = i + 1;
while (low >= 0 && high < s.size() && s[low] == s[high]) {
low--;
high++;
}
string palindromeEven = s.substr(low + 1, high - low - 1);
if (palindromeEven.size() > ans.size()) {
ans = palindromeEven;
}
}
return ans;
}
};
------------------------------------sum of beuty of
substring----------------------------------
The beauty of a string is the difference in frequencies between the most frequent
and least frequent characters.
For example, the beauty of "abaacc" is 3 - 1 = 2.
Input: s = "aabcb"
Output: 5
Explanation: The substrings with non-zero beauty are
["aab","aabc","aabcb","abcb","bcb"], each with beauty equal to 1.
class Solution {
public:
int beautySum(string s) {
int total_beuty=0;
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 maxi=*max_element(freq.begin(),freq.end());
int mini=INT_MAX;
for(int f:freq){
if(f>0){
mini=min(f,mini);
}
}
total_beuty+=(maxi-mini);
}
}
return total_beuty;
}
};
