// Compiled with: g++ -Wall -std=c++14 -pthread

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>

#include <algorithm>

using namespace std;

// Complexity: runtime O(n2), memory O(1)
bool repeated_digits(const std::string& st){

    for (int i = 0; i < st.size(); ++i){
        for (int j = i + 1; j < st.size(); ++j){
            char val0 = st[i];
            char val1 = st[j];
            if (val0 == val1){
                return true;
            }
        }
    }

    return false;
}
//Comments: brute-force or naïve approach


// Complexity: runtime O(nlogn), memory O(1)
bool repeated_digits_sort(std::string& st){
    std::sort(st.begin(), st.end());
    for (int i = 1; i < st.size(); ++i){
        char val0 = st[i];
        char val1 = st[i-1];
        if (val0 == val1){
            return true;
        }
    }

    return false;
}
//Comments: the runtime complexity of sorting algorithms is nlogn
//Comments: runtime complexity = max(nlogn, n)
//Comments: possible to modify st in-place? YES


// Complexity: runtime O(nlogn), memory O(n)
bool repeated_digits_sort_const(const std::string& st){
    std::string st2 = st;
    std::sort(st2.begin(), st2.end());
    for (int i = 1; i < st2.size(); ++i){
        char val0 = st2[i];
        char val1 = st2[i-1];
        if (val0 == val1){
            return true;
        }
    }

    return false;
}
//Comments: the runtime complexity of sorting algorithms is nlogn
//Comments: runtime complexity = max(nlogn, n)
//Comments: possible to modify st in-place? NO


// Complexity: runtime O(n), memory O(1)
bool repeated_digits_hash(const std::string& st){
    unordered_set<char> hashset;

    for (char c : st){
        if (hashset.count(c) == 1) {
            return true;
        }
        hashset.insert(c);
    }

    return false;
}
//Comments: hashset.count() y hashset.insert() have constant runtime
//Comments: for (char c : st) :)

// Complexity: runtime O(1), memory O(1)
bool repeated_digits_smart(const std::string& st) {
    if (st.size() > 10)
        return true;

    return repeated_digits(st);
}
//Comments: important to know that the string contains only numbers


int main(){

    std::vector<std::pair<std::string, bool>> tests = {
        {"", false},
        {"1", false},
        {"5", false},
        {"12", false},
        {"894", false},
        {"0987654321", false},
        {"1324576098", false},
        {"00", true},
        {"12345678901", true}
    };

    for (int i = 0; i < tests.size(); ++i) {
        std::cout<<"TEST "<<i<<std::endl;
        std::string query = tests[i].first;
        bool expected = tests[i].second;
        bool received = repeated_digits_smart(query);

        if (expected == received) {
            std::cout<<"PASSED!"<<std::endl;
        } else {
            std::cout<<" * FAILED! Expected: "<<expected<<". Received: "<<received<<std::endl;
        }
        std::cout<<"-----------------------------"<<std::endl;
    }


    return 0;
}

/*
std::string numeros = "902183901234031892748923651";

Como harias una funcion, que te diga si hay 2 digitos repetidos en la string?

*/