题意分析

需要找到两个字符串的最长公共子序列（按排列组合），并在长度相同的情况下选择字母顺序序最小的结果。

解题思路

首先统计两个字符串中每个字符的出现频率。对于每个字符，其在结果中的出现次数为两个字符串中该字符出现次数的最小值，根据每个字符的公共频率，按字母顺序构建结果字符串，

标程

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string a, b;
    while (getline(cin, a)) {
        if (cin.eof()) break;
        getline(cin, b);
        
        vector<int> count_a(26, 0);
        vector<int> count_b(26, 0);
        
        for (char c : a) {
            count_a[c - 'a']++;
        }
        for (char c : b) {
            count_b[c - 'a']++;
        }
        
        string result;
        for (int i = 0; i < 26; i++) {
            int common = min(count_a[i], count_b[i]);
            result += string(common, 'a' + i);
        }
        
        cout << result << endl;
    }
    return 0;
}

题目回顾

给定两个字符串 $a$ 和 $b$，要求找到最长的字符串 $x$，使得 $x$ 的某个排列是 $a$ 的子序列，同时 $x$ 的某个排列也是 $b$ 的子序列。如果有多个可能的 $x$，选择字母序最小的那个。

解题思路

1. 问题分析：

   • 我们需要找到两个字符串共有的字符，并且这些字符的出现次数受限于两个字符串中的最小出现次数。
   • 例如，如果 $a$ 中有 'a' 出现 2 次，$b$ 中有 'a' 出现 3 次，那么 $x$ 中 'a' 最多可以出现 2 次。
   • 最终 $x$ 是所有这样的字符按字母序排列的结果。

2. 关键观察：

   • 这个问题可以转化为求两个字符串的字符交集（按最小出现次数）。
   • 例如：
     • $a = \text{"pretty"}$，字符统计：{'p':1, 'r':1, 'e':1, 't':2, 'y':1}
     • $b = \text{"women"}$，字符统计：{'w':1, 'o':1, 'm':1, 'e':1, 'n':1}
     • 共有的字符是 'e'，所以 $x = \text{"e"}$。
   • 如果有多个共有字符，按字母序排列。

3. 算法选择：

   • 统计 $a$ 和 $b$ 中每个字符的出现次数。
   • 对于每个字符，取 $a$ 和 $b$ 中较小的出现次数。
   • 将这些字符按字母序排列，构造 $x$。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    int i, j, lena, lenb;
    string a, b, ans;
    while (getline(cin, a), getline(cin, b))
    {
        lena = a.length();
        lenb = b.length();
        ans.clear();
        for (i = 0; i < lena; i++)
            for (j = 0; j < lenb; j++)
                if (a[i] == b[j])
                {
                    ans.push_back(a[i]);
                    b[j] = '-1';
                    break;
                }
        sort(ans.begin(), ans.end());
        cout << ans << endl;
    }
}