The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

Problem link

The reading experience is better on the blog.

1: Problem Statement

You are given two strings, ss and tt (the lengths of both ss and tt do not exceed 10510^5). You are also given some queries (the number of queries does not exceed 10510^5). Each query is a subset of the lowercase letters 'a' through 'r'. For every query, determine whether ss and tt are equal when they contain only the letters given in the query.

2: Analysis

2.1: Brute Force

It is easy to think of a brute-force method. For each query, consider only the characters contained in the set and compare the two strings. However, this requires traversing the strings again for every query, resulting in n2n^2 complexity (nn is both the number of queries and the string length). This method can obtain partial points.

But how can we get the remaining points?

2.2: Simplifying the Problem

Directly solving this problem may be too complicated. We can try simplifying it first and then generalizing the simplified solution to the original problem.

First consider the case where a query contains only two letters. Let them be aa and bb. How do we determine whether two strings containing only aa and bb are equal?

The first thing to consider is whether the numbers of aas and bbs in the two strings are equal. If either count is different, the two strings must be different.

Next, we need to consider the positions of every aa and bb in the strings. If both the positions and counts are correct, the two strings must be equal.

When comparing the positions of aa and bb, we certainly cannot directly compare their indices, because we are comparing their positions after keeping only aa and bb in the two strings. Their indices must change after other characters are removed.

After removing other characters, the index of each character in a string is actually the number of aas before it plus the number of bbs before it (all other characters have been removed).

Of course, checking the indices of every aa and bb in order takes too much time, so we can optimize. For example, it is enough to check that the positions of one of aa and bb are all equal. Since the numbers of aas and bbs are equal in both strings, once the positions of one character are determined, the positions of the other are determined as well (every position that is not aa must be bb).

This check can be simplified further. We can consider only the number of bbs before each aa. Consider the string "baa". If we use the number of bbs before an aa as the index of aa, the indices of the two aas are the same. If we exchange these two aas, the string remains the same, so the fact that their indices are equal does not affect our determination of the positions of aa.

In summary, two strings containing only two characters (assume they are aa and bb) are equal only if:

  • The numbers of aas and bbs are equal.
  • The number of bbs before every aa is equal.

Why do we use this method to determine whether strings are equal?

Because prefix sums let us quickly determine whether two strings containing only two characters are equal.

Considering the two conditions above, to determine whether the number of bbs before every aa is equal (where aa and bb can be any characters), we need to quickly obtain:

  • The number of each character before every position in the original string.
  • Every position of each character in the original string.

For the first problem, we can preprocess with prefix sums.

We create two arrays, char_sum_s[i][j] and char_sum_t[i][j], representing how many characters jj occur from index 00 through index ii (including ii) in strings ss and tt, respectively.

The following code computes them:

1
2
3
4
5
6
7
8
for(int i = 0; i < s.length(); i++){
    char_sum_s[i][s[i] - 'a'] = 1; // Mark it.
}
for(int i = 1; i < s.length(); i++){
    for(int j = 0; j < 20; j++){ // Enumerate characters.
        char_sum_s[i][j] += char_sum_s[i - 1][j]; // Prefix sum.
    }
}

For the second problem, we create two vectors, char_pos_s[i] and char_pos_t[i], representing all positions of character ii in strings ss and tt, respectively, and compute them using:

1
2
3
for(int i = 0; i < s.length(); i++){
    char_pos_s[s[i] - 'a'].push_back(i);
}

2.3: Considering the Original Problem

Now that we can quickly determine whether two strings containing only two characters are equal, let us consider how to apply this to the original problem.

Suppose the two strings were originally equal. There are several ways to make them different:

  • Add a character.
  • Delete a character.
  • Exchange two characters (exchanging two equal characters is equivalent to not exchanging them).

Note: for convenience, call the function that determines whether two strings containing only characters aa and bb are equal isok(a, b).

For the first two changes, the count of some character in the two strings must change. Suppose the added or deleted character is aa. Then isok(a, other character) must return false, because the counts of aa in ss and tt are no longer equal.

Now consider exchanging characters. Suppose the exchanged characters are aa and bb. Then isok(a, b) must also return false, because the strings consisting only of aa and bb in ss and tt must be different.

Therefore, for each query, we only need to enumerate every pair of different characters included in the query and determine whether ss and tt are equal when containing only those two characters.

Remember to store every isok(a, b) result so that it does not need to be recalculated later.

2.3: Complexity Analysis

  • Preprocessing: O(n)O(n).
  • isok(a, b): because we need to know the number of bbs before every aa, we enumerate aa, so the complexity is the number of aas.
  • Processing all isok(a, b) results: O(n)O(n) (nn is the string length), because we enumerate every aa and bb, and the sum of all their counts is the string length.
  • Queries: (number of letters in one query)2×number of queries\text{(number of letters in one query)}^2 \times \text{number of queries}. Since every isok(a, b) result has already been processed, enumerating two different characters in a query only requires returning the result in O(1)O(1) time. We enumerate (number of letters in one query)2\text{(number of letters in one query)}^2 pairs in total.

3: Code

The code contains detailed comments and is relatively fast. See the submission record.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/*Date: 22 - 03-26 16 22
PROBLEM_NUM: Subset Equality*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
string s, t;
int q;

vector<int> char_pos_s[20], char_pos_t[20];
int char_sum_s[MAXN][20], char_sum_t[MAXN][20]; 
short isok_result[20][20];

bool ans[MAXN];

bool isok(char a, char b){// Determine whether s and t are equivalent when containing only a and b.
    if(isok_result[a][b] != -1 || isok_result[b][a] != -1){// If already calculated, return directly. Note that isok(a, b) == isok(b, a).
        return isok_result[a][b];
    }

    if(a == b){// If a and b are equal, return whether this character occurs equally often in both strings.
        return isok_result[a][b] = (char_pos_s[a].size() == char_pos_t[a].size());
    }

    if(char_pos_s[a].size() != char_pos_t[a].size() || char_pos_s[b].size() != char_pos_t[b].size()){// If the numbers of a and b differ between s and t, return false.
        return isok_result[a][b] = false;
    }

    vector<int> b_cnt_s;// The number of b characters before each a in s.

    for(int cur_apos : char_pos_s[a]){ // Enumerate the positions of a in s.
        b_cnt_s.push_back(char_sum_s[cur_apos][b]);
    }

    for(int i = 0; i < char_pos_t[a].size(); i++){// Enumerate the positions of a in t and compare the number of b characters before them
                                                  // with the corresponding number before a in s.
        if(char_sum_t[char_pos_t[a][i]][b] != b_cnt_s[i]){
            return isok_result[a][b] = false;
        }
    }
    return isok_result[a][b] = true;
}

void pre_proc(){
    for(int i = 0; i < s.length(); i++){
        char_pos_s[s[i] - 'a'].push_back(i);
        char_sum_s[i][s[i] - 'a'] = 1; // Mark it.
    }

    for(int i = 0; i < t.length(); i++){
        char_pos_t[t[i] - 'a'].push_back(i);
        char_sum_t[i][t[i] - 'a'] = 1;
    }

    for(int i = 1; i < s.length(); i++)// Prefix sum of s.
        for(int j = 0; j < 20; j++)
            char_sum_s[i][j] += char_sum_s[i - 1][j];

    for(int i = 1; i < t.length(); i++)// Prefix sum of t.
        for(int j = 0; j < 20; j++)   // j is a character.
            char_sum_t[i][j] += char_sum_t[i - 1][j];

    for(int i = 0; i < 20; i++)
        for(int j = 0; j < 20; j++)
            isok_result[i][j] = -1;// Set to -1 when not calculated.
}

int main(){
    ios::sync_with_stdio(false);
    cin>>s>>t>>q;
    
    pre_proc();// Preprocess.

    for(int i = 1; i <= q; i++){// Enumerate every character in each query.
        string cur_query;
        cin>>cur_query;
        ans[i] = true;
        for(char char_a : cur_query){
            for(char char_b : cur_query){
                if(!isok(char_a - 'a', char_b - 'a')){ // If any isok(a, b) == false, s and t are not equivalent when containing only the query's characters.
                    ans[i] = false;
                    break;
                }
            }
            if(!ans[i]) break;
        }
    }

    for(int i = 1; i <= q; i++){
        if(ans[i])
            cout<<"Y";
        else
            cout<<"N";
    }
    system("pause");
}

Finally, I hope this solution is helpful. If there is anything you do not understand or you find a problem with the solution, feel free to contact me through the comments or a private message.