题面描述

给定两个字符串 string1 和 string2。string1 是一个被加扰的字符串。

• string1 由小写英文字母（'a' ~ 'z'）和数字字符（'0' ~ '9'）组成，而加扰字符串由 '0' ~ '9'、'a' ~ 'f' 组成。
• string1 里面可能包含 0 个或多个加扰子串，剩下可能有 0 个或多个有效子串，这些有效子串被加扰子串隔开。
• string2 是一个参考字符串，仅由小写英文字母（'a' ~ 'z'）组成。

你需要在 string1 字符串里找到一个有效子串，这个有效子串要同时满足以下两个条件：

1. 这个有效子串里不同字母的数量不超过且最接近于 string2 里不同字母的数量，即小于或等于 string2 里不同字母的数量的同时且最大。
2. 这个有效子串是满足条件（1）里的所有子串（如果有多个的话）里字典序最大的一个。

如果没有找到合适条件的子串的话，请输出 "Not Found"。

思路

1. 提取有效子串：

   • 遍历 string1，将其分割为加扰子串和有效子串。
   • 加扰子串由字符 '0' ~ '9' 和 'a' ~ 'f' 组成，其他字符组成有效子串。
   • 提取所有有效子串并存储。

2. 计算参考字符串的不同字母数量：

   • 遍历 string2，统计其中不同字母的数量。

3. 筛选符合条件的有效子串：

   • 对于每个有效子串，计算其不同字母的数量。
   • 筛选出不同字母数量不超过参考数量且最大接近参考数量的子串。

4. 选择字典序最大的子串：

   • 在筛选出的子串中，选择字典序最大的一个。

5. 处理无符合条件的情况：

   • 如果没有符合条件的子串，输出 "Not Found"。

代码分析

• 提取有效子串：

  • 使用指针遍历 string1，根据字符是否属于加扰字符集来分割字符串。

• 计算不同字母数量：

  • 使用 set 或 unordered_set 来统计不同字母的数量。

• 筛选和选择：

  • 遍历所有有效子串，记录符合条件的子串。
  • 使用变量记录当前最大符合条件的不同字母数量以及对应的字典序最大的子串。

• 优化：

  • 可以在遍历过程中实时更新符合条件的最大值，减少存储空间。

cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
    string string1, string2;
    cin >> string1 >> string2;
    
    // 提取 string2 中不同字母的数量
    unordered_set<char> ref_set;
    for(char c : string2){
        ref_set.insert(c);
    }
    int ref_unique = ref_set.size();
    
    // 提取 string1 中的所有有效子串
    vector<string> valid_substrings;
    string current;
    for(char c : string1){
        // 判断是否为加扰字符（'0'-'9' 或 'a'-'f'）
        if( (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') ){
            // 遇到加扰字符，结束当前有效子串
            if(!current.empty()){
                valid_substrings.push_back(current);
                current.clear();
            }
        }
        else{
            // 有效字符，加入当前子串
            current += c;
        }
    }
    // 最后检查是否有剩余的有效子串
    if(!current.empty()){
        valid_substrings.push_back(current);
    }
    
    // 初始化结果变量，记录最大不同字母数量和对应的子串
    int max_unique = -1;
    string result = "";
    
    // 遍历所有有效子串
    for(auto &s : valid_substrings){
        // 使用 unordered_set 统计不同字母的数量
        unordered_set<char> s_set(s.begin(), s.end());
        int unique_cnt = s_set.size();
        
        // 检查是否满足条件（不同字母数量 <= 参考数量）
        if(unique_cnt <= ref_unique){
            if(unique_cnt > max_unique){
                // 更新最大不同字母数量和结果子串
                max_unique = unique_cnt;
                result = s;
            }
            else if(unique_cnt == max_unique){
                // 如果数量相同，选择字典序较大的子串
                if(s > result){
                    result = s;
                }
            }
        }
    }
    
    // 输出结果，如果没有符合条件的子串，输出 "Not Found"
    if(max_unique == -1){
        cout << "Not Found";
    }
    else{
        cout << result;
    }
}

python

import sys

def main():
    # 读取输入的两个字符串
    input_data = sys.stdin.read().split()
    if len(input_data) < 2:
        string1 = input_data[0] if len(input_data) > 0 else ""
        string2 = ""
    else:
        string1, string2 = input_data[0], input_data[1]
    
    # 提取 string2 中不同字母的数量
    ref_set = set()
    for c in string2:
        ref_set.add(c)
    ref_unique = len(ref_set)
    
    # 提取 string1 中的所有有效子串
    valid_substrings = []
    current = ""
    for c in string1:
        # 判断是否为加扰字符（'0'-'9' 或 'a'-'f'）
        if ('0' <= c <= '9') or ('a' <= c <= 'f'):
            # 遇到加扰字符，结束当前有效子串
            if current:
                valid_substrings.append(current)
                current = ""
        else:
            # 有效字符，加入当前子串
            current += c
    # 最后检查是否有剩余的有效子串
    if current:
        valid_substrings.append(current)
    
    # 初始化结果变量，记录最大不同字母数量和对应的子串
    max_unique = -1
    result = ""
    
    # 遍历所有有效子串
    for s in valid_substrings:
        # 使用 set 统计不同字母的数量
        s_set = set(s)
        unique_cnt = len(s_set)
        
        # 检查是否满足条件（不同字母数量 <= 参考数量）
        if unique_cnt <= ref_unique:
            if unique_cnt > max_unique:
                # 更新最大不同字母数量和结果子串
                max_unique = unique_cnt
                result = s
            elif unique_cnt == max_unique:
                # 如果数量相同，选择字典序较大的子串
                if s > result:
                    result = s
    
    # 输出结果，如果没有符合条件的子串，输出 "Not Found"
    if max_unique == -1:
        print("Not Found")
    else:
        print(result)

if __name__ == "__main__":
    main()

java

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String string1 = sc.next(); // 读取第一个字符串
        String string2 = sc.next(); // 读取第二个字符串
        
        // 计算参考字符串中不同字母的数量
        Set<Character> refSet = new HashSet<>();
        for(char c : string2.toCharArray()){
            refSet.add(c);
        }
        int refUnique = refSet.size();
        
        // 提取有效子串
        List<String> validSubstrings = new ArrayList<>();
        StringBuilder current = new StringBuilder();
        for(char c : string1.toCharArray()){
            // 判断是否为加扰字符（'0'-'9' 或 'a'-'f'）
            if( ('0' <= c && c <= '9') || ('a' <= c && c <= 'f') ){
                // 遇到加扰字符，结束当前有效子串
                if(current.length() > 0){
                    validSubstrings.add(current.toString());
                    current.setLength(0); // 清空当前子串
                }
            }
            else{
                // 有效字符，加入当前子串
                current.append(c);
            }
        }
        // 最后检查是否有剩余的有效子串
        if(current.length() > 0){
            validSubstrings.add(current.toString());
        }
        
        // 初始化结果变量，记录最大不同字母数量和对应的子串
        int maxUnique = -1;
        String result = "";
        
        // 遍历所有有效子串
        for(String s : validSubstrings){
            Set<Character> sSet = new HashSet<>();
            for(char c : s.toCharArray()){
                sSet.add(c);
            }
            int uniqueCnt = sSet.size(); // 统计不同字母的数量
            
            if(uniqueCnt <= refUnique){
                if(uniqueCnt > maxUnique){
                    // 更新最大不同字母数量和结果子串
                    maxUnique = uniqueCnt;
                    result = s;
                }
                else if(uniqueCnt == maxUnique){
                    // 如果数量相同，选择字典序较大的子串
                    if(s.compareTo(result) > 0){
                        result = s;
                    }
                }
            }
        }
        
        // 输出结果，如果没有符合条件的子串，输出 "Not Found"
        if(maxUnique == -1){
            System.out.println("Not Found");
        }
        else{
            System.out.println(result);
        }
    }
}

题目内容

给定两个字符串 $string1$ 和 $string2$。 $string1$ 是一个被加扰的字符串。

$string1$ 由小写英文字母$（’a’~ ’z’）$和数字字符$（’0’~ ’9’）$组成，而加扰字符串由$’0’~ ’9’、’a’~’f’$组成。

$string1$ 里面可能包含 $0$ 个或多个加扰子串，剩下可能有 $0$ 个或多个有效子串，这些有效子串被加扰子串隔开。

$string2$ 是一个参考字符串，仅由小写英文字母$（’a’~’z’）$组成。

你需要在 $string1$ 字符串里找到一个有效子串，这个有效子串要同时满足下面两个条件：

（1）这个有效子串里不同字母的数量不超过且最接近于 $string2$ 里不同字母的数量，即小于或等于$string2$ 里不同字母的数量的同时且最大。

（2）这个有效子串是满足条件（1）里的所有子串（如果有多个的话）里字典序最大的一个。

如果没有找到合适条件的子串的话，请输出“$Not$ $Found$”

输入描述

$input_string1$ $input_string2$

输出描述

$output_string$

样例1

输入

123admyffc79pt
ssyy

输出

pt

说明

将输入字符串 $1$ 里的加扰子串“$123ad$”、“$ffc79$”去除后得到有效子串序列：$"my"、"pt"$，其中"$my$"里不同字母的数量为 $2$ （有‘$m$’和'$y$'两个不同字母），“$pt$”里不同字母的数量为 $2$（有'$p$'和'$t$'两个不同字母）；输入字符串 $2$ 里不同字母的数量为 $2$ （有‘$s$’和'$y$'两个不同字母）。

可得到最终输出结果为“$pt$”，其不同字母的数量最接近与“$ssyy$”里不同字母的数量的同时字典序最大。

样例2

输入

123admyffc79ptaagghi2222smeersst88mnrt
ssyyfgh

输出

mnrt

说明

将输入字符串 $1$ 里的加扰子串 $“123ad”、“ffc79”、"aa"、"2222"、"ee"、"88"$ 去除后得到有效子串序列：$“my”、“pt”、“gghi”、"sm"、“rsst”、"mnrt"$；

输入字符串 $2$ 里不同字母的数量为 $5$（有$'s'、'y'、'f'、'g'、'h' 5$个不同字母）。

可得到最终输出结果为“$mnrt$”，其不同字母的数量（为$4$）最接近于“$ssyyfgh$”里不同字母的数量，其他有效子串不同字母的数量都小于“$mnrt$”。

样例3

输入

abcmnq
rt

输出

Not Found

说明

将输入字符串 $1$ 里的加扰子串 “$abc$” 去除后得到有效子串序列：“$mnq$”；

输入字符串 $2$ 里不同字母的数量为 $2$（有$'r'、't'$ 两个不同的字母）。

可得到最终的输出结果为“$Not$ $Found$”，没有符合要求的有效子串，因有效子串里的不同字母的数量（为$3$），大于输入字符串 $2$ 里的不同字母的数量。