UVa 10252 – Common Permutation
Given two strings a and b consisting of lowercase letters.
Print the longest lowercase string x, such that x is a subsequence of an after rearrangement, and x is a subsequence of b after rearrangement.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| Input ends with EOF. Each pair of consecutive lines represents a test case, where the first line is the string a and the second line is the string b. Each pair of consecutive lines represents a test case. The first and second lines form one test case, the third and fourth lines form another test case, and so on. Each string contains at most 1000 lowercase letters. | For each pair of inputs, output the required x for a and b. If there are multiple matching x's, print the one with the letters in ascending order. |
| pretty women walking down the street | e nw et |
Thought Process
Use a Map to record the characters in string a. Then iterate through string b using a for loop. Check if each character in b exists in the Map for a. If it does, record it in the answer Map and decrement the count in the Map for a.
Iterate through the answer Map using a for loop like this: for (auto it : Map). Output the characters from the answer Map.
Sample Code－ZeroJudge E507: Common Permutation
#include <iostream>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
string a, b;
while (cin >> a >> b)
{
map<char, int>A;
map<char, int>ans;
for (int i = 0; i<a.length(); i++)
{
A[a[i]]++;
}
for (int i = 0; i<b.length(); i++)
{
if (A[b[i]] > 0)
{
ans[b[i]]++;
A[b[i]]--;
}
}
for (auto it:ans)
{
for (int i = 0; i<it.second; i++)
{
cout << it.first;
}
}
cout << "\n";
}
}
//ZeroJudge E507
//Dr. SeanXD