Untitled

/*
Написать метод, который заменит все пробелы в строке на "%20" inplace.

На вход подается строка с зарезервированными под расширение символами
(гарантируется, что resize до разумных размеров не будет аллоцировать память).
,*/

void urlify(std::string& s){
    if (s.empty()){
        return;
    }
    size_t spaces = 0;
    for (auto c: s){
        if (c == ' '){
            ++spaces;
        }
    }

    size_t size = s.size();
    s.resize(s.size() + 2 * spaces);
    for (size_t i = size - 1; i >= 0; --i){
        if (i == 0){
            if (s[i] == ' '){
                s[i] = '%';
                s[i + 1] = '2';
                s[i + 2] = '0';
            }
            break;
        }
        if (s[i] == ' '){
            s[i] = '%';
            s[i + 1] = '2';
            s[i + 2] = '0'; 
            --spaces;
            if (spaces == 0){
                return;
            }
        } else {
            s[i + spaces * 2] = s[i];
        }
    }
}

std::string s0 = "my url";
std::string s0 = "my%20url";
s0.reserve(20);

urlify(s0);
assert(s0 == "my%20url");










/*

Дано бинарное дерево с выделенным корнем, в каждой вершине которого записано по одной букве A-Z.

Две вершины считаются эквивалентными, если поддеревья этих вершин содержат одинаковое множество (т.е. без учета частот) букв.

В примере ниже эквивалентными являются вершины B и C -- прямые потомки корня А (Плюсами помечены эквивалентные вершины):

      A
    /   \
   C+    B+
  / \   / \
  A D   A  D
 /          \
B            C

      A
    /   \
   X+    B+
  / \   / \
  F D   F  D
 /          \
B+            B+
              \
               B


      A
    /   \
   X+    B+
        / \
        F  D
            \
             B+
              \
               B


            
*/

struct TNode {
    char Value = '\0';  // [A-Z]
    TNode* Left = nullptr;
    TNode* Right = nullptr;
};
std::pair<TNode*, TNode*> FindEquivalentSubtrees(TNode* root){
    if (root == nullptr){
        return {nullptr, nullptr};
    }
    std::unordered_map<unsigned int, TNode*> sets;
    std::pair<TNode*, TNode*> answer;
    auto ret_val = recursive(root, sets, answer);
    return answer;
}

unsigned int recursive(TNode *root, std::unorded_map<unsigned int, TNode*> &sets, std::pair<TNode*, TNode*> &answer){
    if (answer.first != nullptr){
        return 0;
    }
    if (root == nullptr){
        return 0;
    }
    unsigned int curSet = 1 << (root->Value - 'A');
    unsigned int leftSet = recursive(root->Left, sets, answer);
    unsigned int rightSet = recursive(root->Right, sets, answer);
    curSet = curSet | leftSet | rightSet;
    if (sets.contains(curSet)){
        
        answer.first = root;
        answer.second = sets[curSet];
    } else{
        sets[curSet] = root;
    }
    return curSet;
}