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