763. Разметка разделов (Partition Labels)

Задание.

Дана строка s.

Нужно разделить строку на как можно большее количество частей, чтобы каждая буква появлялась не более чем в одной части.

Обратите внимание, что разбиение выполнено таким образом, что после объединения всех частей по порядку результирующей строкой будет s.

Верните вектор чисел, представляющих размер этих частей.

Пример 1.

Входные данные: s = “ababcbacadefegdehijhklij”

Результат: [9,7,8]

Пояснение: Разделение – “ababcbaca”, “defegde”, “hijhklij”. Это разбиение таким образом, чтобы каждая буква появлялась не более чем в одной части. Разделение “ababcbacadefegde”, “hijhklij” не подходит, поскольку разбивает s на меньшее количество частей.

Пример 2.

Входные данные: s = “eccbbbbdec”

Результат: [10]

Решение.

class Solution {
public:
    vector<int> partitionLabels(string s) {
        unordered_map<char, int> lp;
        vector<int>ans;
        int n = s.length();

        for(int i = 0; i < n; i++) {
            lp[s[i]] = i;
        }

        // i указывает на начало фрагмента
        // lp[ s[i] ] указывает на последнее вхождение символа
        int maxExtend = 0; // указывает на конец последовательности
        int prev = -1; // указывает на индекс завершения предыдущей последовательности

        for(int i = 0; i < n; i++) {
            maxExtend = max( maxExtend, lp[s[i]] );
            if(maxExtend == n-1) {
                ans.push_back(maxExtend - prev);
                break;
            } else if(maxExtend == i) {
                ans.push_back(i - prev);
                prev = i;
                maxExtend = 0;
            }
        }
        return ans;
    }
};

Способ решения.

1) Сначала для каждого символа в строке определяется последняя позиция, в которой этот символ встречается в строке.

2) Затем ищутся последовательности. Для начального символа последовательности (который отмечается индексом i) определяется maxExtend, который указывет на индекс завершения последовательности.

Так, например, для символа a индекс завершения будет 8, то есть индекс, в котором a последний раз встречается в строке.

Когда индекс i совпадёт с maxExtend – это будет означать, что последовательность определена и можно запомнить её размер, после чего можно перейти к определению следующей последовательности.

Указатель prev отмечает индекс завершения предыдущей последовательности.

При определении последовательности, maxExtend может увеличиваться в соответствии с индексом завершения символов, который входят в последовательность. Так например, для второй последовательности при рассмотрении символа d будет установлен maxExtend = 14, на следующем шаге при рассмотрении символа e будет установлен maxExtend = 15. Другие символы не будут приводить к расширению maxExtend.