String Obsession
Problem Description
Who knows the reason for why little Meera is so obsessed with strings and loves to
spend her time analyzing them!?
Meera has an everlasting passion for strings. One day, she took a string (let us
call it the main string) along with some substrings and decided to remove as many
substrings from the main string as possible. Whenever a part is removed, the
remaining portions of the string are joined together. For example, if the main
string is "hello" and "el" is removed, it becomes "hlo." Note that she can remove
one substring only once from the string.
Given the main string and the substrings, determine and print the maximum number of
substrings that can be removed.
Constraints
1 <= length of main string <= 55
1 <= length of each substring <= 15
Both main and substrings will be having only lower-case alphabets only.
Input
First line consists of N, denoting the total number of substrings.
Next line consists of N space separated substrings.
Last line consists of the main string.
Output
Print a single integer denoting the maximum number of substrings that can be
removed.
Time Limit (secs)
1
Examples
Example 1
Input
hd el llo wor ell lds
helloworlds
Output
Explanation
Given main string is - helloworlds
Remove llo, the string becomes heworlds
Remove wor, the string becomes helds
Remove el, the string becomes hds
Remove hd, the string becomes s. One cannot remove anything further.
Hence the maximum number of substrings we can remove is 4, print 4 as output.
Example 2
Input
ggc rm oo le glh oog ec
googlechrome
Output
Explanation
Given main string is - googlechrome
Remove oo, the string becomes gglechrome
Remove le, the string becomes ggchrome
Remove ggc, the string becomes hrome. One cannot remove anything further.
Second possibility can also be - removing ec,glh,oo resulting in grome, further
reduction is impossible. In this case also only 3 substrings have been removed.
Hence the maximum number of substrings we can remove is 3, hence print 3 as output
ANSWER:
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int maximizePlacement(string& input, vector<string>& substrs, unordered_map<string,
int>& cache) {
if ([Link](input)) return cache[input];
int maxPlacements = 0;
for (auto& substr : substrs) {
size_t position = [Link](substr);
if (position != string::npos) {
string newInput = [Link](0, position) + [Link](position +
[Link]());
maxPlacements = max(maxPlacements, 1 + maximizePlacement(newInput,
substrs, cache));
}
}
return cache[input] = maxPlacements;
}
int main() {
int substringCount;
cin >> substringCount;
vector<string> substrings(substringCount);
for (int i = 0; i < substringCount; ++i) {
cin >> substrings[i];
}
string mainStr;
cin >> mainStr;
unordered_map<string, int> memoization;
cout << maximizePlacement(mainStr, substrings, memoization);
return 0;
}