In a recent online assessment I was asked the following question:↵
===================================================================↵
You are given a string consisting of lower case letters only. You are allowed to remove one or more consecutive characters if they are similar. For each removal of character/characters you get points based on number of characters removed and points_array. You have to continue this process till the string is empty. ↵
If n characters removed then: points = points_array[n] ( 1 based indexing ).↵
You have to maximize the total points earned.↵
↵
Example:↵
s = "aabaabaa"↵
points_array = [1, 2, 1, 1, 1, 10, 1, 1]↵
↵
_s -> "aabaabaa"_↵
↵
_s -> "aaaabaa" +1 ( removed "b" )_↵
↵
_s -> "aaaaaa" +1 ( removed "b" )_↵
↵
_s -> "" +10 ( removed "aaaaaa" )_↵
↵
points earned are 12↵
↵
Constraints:↵
↵
**1 <= len(s) <= 100**↵
↵
**len(points_array) == len(s)**↵
↵
**0 <= points_array[i] <= 10^6**↵
↵
#### I was able to figure out recursive solution using stack:↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <stack>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
int recUtil(stack<int> st, vector<int> &points, string s, int ind)↵
{↵
if (ind == s.size())↵
{↵
if (st.size() == 0)↵
{↵
return 0;↵
}↵
char top = st.top();↵
st.pop();↵
int ans = points[0] + recUtil(st, points, s, ind);↵
int count = 1;↵
while (!st.empty() && st.top() == top)↵
{↵
st.pop();↵
count += 1;↵
ans = max(ans, points[count - 1] + recUtil(st, points, s, ind));↵
}↵
return ans;↵
}↵
else↵
{↵
st.push(s[ind]);↵
int ans = recUtil(st, points, s, ind + 1);↵
char top = st.top();↵
st.pop();↵
ans = max(ans, points[0] + recUtil(st, points, s, ind + 1));↵
int count = 1;↵
while (!st.empty() && st.top() == top)↵
{↵
st.pop();↵
count += 1;↵
ans = max(ans, points[count - 1] + recUtil(st, points, s, ind + 1));↵
}↵
return ans;↵
}↵
}↵
int main()↵
{↵
string s = "abbbacabbba";↵
vector<int> points = {1, 8, 10, 7, 6, 4, 8, 0, 8, 5, 9};↵
stack<int> st;↵
cout << recUtil(st, points, s, 0) << endl;↵
return 0;↵
}↵
~~~~~↵
↵
**Any suggestions or editorial to solve such problem optimally**↵
↵
↵
↵
===================================================================↵
You are given a string consisting of lower case letters only. You are allowed to remove one or more consecutive characters if they are similar. For each removal of character/characters you get points based on number of characters removed and points_array. You have to continue this process till the string is empty. ↵
If n characters removed then: points = points_array[n] ( 1 based indexing ).↵
You have to maximize the total points earned.↵
↵
Example:↵
s = "aabaabaa"↵
points_array = [1, 2, 1, 1, 1, 10, 1, 1]↵
↵
_s -> "aabaabaa"_↵
↵
_s -> "aaaabaa" +1 ( removed "b" )_↵
↵
_s -> "aaaaaa" +1 ( removed "b" )_↵
↵
_s -> "" +10 ( removed "aaaaaa" )_↵
↵
points earned are 12↵
↵
Constraints:↵
↵
**1 <= len(s) <= 100**↵
↵
**len(points_array) == len(s)**↵
↵
**0 <= points_array[i] <= 10^6**↵
↵
#### I was able to figure out recursive solution using stack:↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <stack>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
int recUtil(stack<int> st, vector<int> &points, string s, int ind)↵
{↵
if (ind == s.size())↵
{↵
if (st.size() == 0)↵
{↵
return 0;↵
}↵
char top = st.top();↵
st.pop();↵
int ans = points[0] + recUtil(st, points, s, ind);↵
int count = 1;↵
while (!st.empty() && st.top() == top)↵
{↵
st.pop();↵
count += 1;↵
ans = max(ans, points[count - 1] + recUtil(st, points, s, ind));↵
}↵
return ans;↵
}↵
else↵
{↵
st.push(s[ind]);↵
int ans = recUtil(st, points, s, ind + 1);↵
char top = st.top();↵
st.pop();↵
ans = max(ans, points[0] + recUtil(st, points, s, ind + 1));↵
int count = 1;↵
while (!st.empty() && st.top() == top)↵
{↵
st.pop();↵
count += 1;↵
ans = max(ans, points[count - 1] + recUtil(st, points, s, ind + 1));↵
}↵
return ans;↵
}↵
}↵
int main()↵
{↵
string s = "abbbacabbba";↵
vector<int> points = {1, 8, 10, 7, 6, 4, 8, 0, 8, 5, 9};↵
stack<int> st;↵
cout << recUtil(st, points, s, 0) << endl;↵
return 0;↵
}↵
~~~~~↵
↵
**Any suggestions or editorial to solve such problem optimally**↵
↵
↵
↵
