ZeroJudge O078: Word Vacancy

Given a set of K letters and a string S, find the lexicographically smallest string of length L that is not a substring of S, using the given set.

For example, for the letter set {a, c, m}, the sorted list of strings of length 2 is: aa < ac < am < ca < cc < cm < ma < mc < mm. If the string S is "accaamcm", then "ma" is the lexicographically smallest string that is not a substring of S.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains a lowercase string of length K (1 <= K <= 10) representing the letter set. The characters are guaranteed to be unique and sorted in ascending order.
The second line contains a positive integer L (1 <= L <= 8, 1 <= K^L <= 6 * 10^5).
The third line contains a lowercase English string S (L <= |S| <= 5 * 10^5).		Output the smallest lexicographically string that satisfies the given conditions.
acm
2
accaamcm		ma
dp
3
dddppdpd		pdd

Thought Process

Use DFS to calculate all combinations. Because there can be duplicate characters, the DFS function only needs the current concatenated string as a parameter. Declare a Map to record the combinations, named MAP. When the length of the string in DFS == L, MAP[string]++ and return.

Run a for loop from 0 to S.length() - L, and declare another Map to record the substrings of length L in S, named appear. Inside, run another for loop from the current position i to i+L, concatenating strings from the current position to the length L. After concatenation, an increment appear[just concatenated string]++.

Afterward, run a for loop for (auto it : MAP), where you need to check all combinations in K. If appear[it.first] == 0, it means that S does not have this substring, but DFS just calculated this it.first. This is the answer, so output it.first and break the loop. When running for (auto it : MAP), it will iterate through the strings in order, so the first one encountered will be the smallest lexicographical string.

Sample Code－ZeroJudge O078: Word Vacancy

#include <iostream>
#include <map>
using namespace std;

string K, str;
int L;
map<string, int>MAP;

void DFS(string add) {
    if (add.length() == L) {
        MAP[add]++;
        return;
    }
    for (int i = 0; i<K.length(); i++) DFS(add+K[i]);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> K >> L >> str;
    DFS("");
    map<string, int>appear;
    for (int i = 0; i<=str.length()-L; i++) {
        string tmp = "";
        for (int j = i; j<i+L; j++) tmp += str[j];
        appear[tmp]++;
    }
    for (auto it:MAP) {
        if (appear[it.first] == 0) {
            cout << it.first << "\n";
            break;
        }
    }
}

//ZeroJudge O078
//Dr. SeanXD
Tags

Related Posts

Comments