题解 | #LUCKY STRING# 集合

首先理解题意：

如字符串aabbcde中，一共有abcde五种字母，而5是斐波那契数，因此这个子串可以被输出；

如字符串aabbcdef中，一共有abcdef六种字母，而6不是斐波那契数，因此这个子串不能被输出

那么接下来处理好逻辑就行了：

先生成给定字符串的所有子串，再分别对每一个子串统计其字母种类数，再判断是不是斐波那契数即可

注意unordered_set无序，而set自带排序，因此无需再排

#include <iostream>
#include <set>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    string s;
    cin >> s;

    // 一共26种字母，因此记录26内的斐波那契数，便于查表
    unordered_set<int> fibonacci = {1, 2, 3, 5, 8, 13, 21};

    // 生成字符串s的所有子串
    unordered_set<string> substrings;
    for (int i = 1; i <= s.size(); i++) {
        for (int j = 0; j < s.size() - i + 1; j++) {
            substrings.insert(s.substr(j, i));
        }
    }
    
    unordered_set<char> kinds; // 存储子串字母的种类数
    set<string> ans;
    for (const auto& substring : substrings) {
        kinds.clear(); // 注意每次判断一个新的子串要清空集合
        // 将子串的各个字母插入到集合中去重
        for (char ch : substring) {
            kinds.insert(ch);
        }
        // 判断这个数量是否是斐波那契数
        if (fibonacci.find(kinds.size()) != fibonacci.end()) {
            ans.insert(substring);
        }
    }

    for (const auto& str : ans) {
        cout << str << endl;
    }
    return 0;
}

时间复杂度：O(n^2)，其中n是给定的字符串长度，主要用于生成子串

空间复杂度：O(n^2)，其中n是给定的字符串长度，主要用于存储子串