// Дан не пустой массив из нулей и единиц. Нужно определить, какой максимальный по длине подинтервал единиц можно получить, удалив ровно один элемент массива.
int getMaxLength(const std::vector<int>& arr) {
    size_t maxLength = 0U;
    
    size_t lastZeroIndex;
    
    size_t length = 0U;
    bool isZeroMissed = false;
    
    for (size_t i = 0U; i < arr.size(); ++i) {
        if (arr[i] == 0) {
            if (isZeroMissed) {
                if (length > maxLength) maxLength = length;
                i = lastZeroIndex;
                length = 0U;
                isZeroMissed = false;
            }else {
                lastZeroIndex = i;
                isZeroMissed = true;
            }
        }else {
            length += 1U;
        }
    }
    
    if (length > maxLength) maxLength = length;
    
    if (maxLength == arr.size()) maxLength -= 1;
    
    return maxLength;
}
// Проверка:
// {1} => 0
// {0} => 0
// {1, 1, 1} => 2
// {0, 0, 0} => 0
// {1, 0, 1, 1} => 3
// {0, 1, 1, 0} => 2
// {1, 0, 0, 1} => 1





// Дан текст T и строка S. Требуется найти подстроку S' в T такую, что она совпадает с S с точностью до перестановки букв.
bool getSubstr(conts std::string& text, conts std::string& str) {
    if (str.size() > text.size()) return false;
    
    // key - символ, value - кол-во вхождение в строку
    const std::unordered_map<char, int> needle;
    for (auto symbol : str) {
        needle[symbol]++;
    }
    
    std::unordered_map<char, int> haystack;
    for (size_t i = 0U; i < str.size(); ++i) {
        char symbol = text[i];
        haystack[symbol]++;
    }
    
    for (size_t i = 0U; i < text.size() - str.size(); ++i) {
        if (needle = haystack) return true;
        
        // Убираем первый символ из подстроки в тексте
        auto it = haystack.find(text[i]);
        if (it->second == 1) {
            haystack.erase(it);
        }else {
            (it->second)--;
        }
        
        // Добавляем новый символ
        auto symbol = text[i + str.size()];
        haystack[symbol]++;
    }
    
    if (needle = haystack) return true;
    
    return false;
}
// Проверка:
// "a"    "a"    => true 
// "abcd", "aaa" => false ?
// "abcd", "cbd" => true
// "abcdda", "bcdd" => true ? 




// Развернуть односвязанный список
struct ListNode {
    ListNode* next;
}

ListNode* getReverse(ListNode* list) {
    if (list == nullptr) return nullptr;
    
    ListNode* prev     = nullptr;
    ListNode* current  = list;
    ListNode* next     = list->next;
    
    while (next != nullptr) {
        current->next = prev;
        
        prev    = current;
        current = next;
        next    = next->next;
    }
    
    current->next = prev;
    
    return current;
}





// Дано дерево с выделенным корнем.
// Далее приходит K запросов, каждый запрос - целое неотрицательное число,
// расстояние от корня. Для каждого запроса нужно найти сумму элементов в дереве
// на расстоянии от корня не более заданного.
struct Node {
    int value;
    Node* l;
    Node* r;
};

class Handler {
private:
    // Для каждого уровня храним сумму элементов
    std::unordered_map<size_t, int> _sum;

    size_t _maxLevel;

    void calculateDepthSum(Node* node, size_t level) {
        if (node == nullptr) return;
        
        if (level > max_Level) _maxLevel = level;
        
        _sum[level] += node->value;
        
        calculateDepthSum(node->r, level + 1);
        calculateDepthSum(node->l, level + 1);
    }
    
    void calculateTotalSum() {
        for (size_t level = 0U; level < _maxLevel; ++level) {
            _sum[level + 1U] += _sum[level];
        }
    }

public:
    void init(Node* tree) {
        _maxLevel = 0U;
        _sum[0U]  = 0;

        calculateDepthSum(tree, 0U);
        calculateTotalSum();
    }
    
    
    int sum(size_t level) const {
        if (level > _maxLevel) return _sum[_maxLevel];
        
        return _sum[level];
    }
};
// Проверка:
//       1
//   2       3
// 4   5   
//        6
// _maxLevel = 3
// _sum[0U] = 1
// _sum[1U] = 5 + 1
// _sum[2U] = 9 + (5 + 1)
// _sum[3U] = 6 + (9 + 5 + 1)







// Дано бинарное дерево с выделенным корнем, в каждой вершине которого записано по одной букве A-Z.
// Две вершины считаются эквивалентными, если поддеревья этих вершин содержат одинаковое множество (т.е. без учета частот) букв.
// Нужно найти любую пару эквивалентных вершин.
struct TNode {
    char Value;
    TNode* Left = nullptr;
    TNode* Right = nullptr;
};

std::unordered_multimap<int, Node*> set;

std::pair<TNode*, TNode*> FindEquivalentSubtrees(TNode* root) {
    int value = 0U;

    if (root->Left != nullptr) {
        int left = FindEquivalentSubtrees(root->Left);
    
        
        auto it = set.find(left);
        if (it != set.end()) {
            return {*it, root};
        }else {
            value |= left;
        }
    }
    if (root->Right != nullptr) {
        int right = FindEquivalentSubtrees(root->Right);
        
        auto it = set.find(right);
        if (it != set.end()) {
            return {*it, root};
        }else {
            value |= rigth;
        }
    }
    
    // Добавляем бит у индекса root->value;
    value |= 1 << (root->Value - 'A');
    
    return value;
}