Пространственная сложность задачи метки раздела

Question

Задана строка S из строчных букв.Мы хотим разбить эту строку на максимально возможное количество частей, чтобы каждая буква появлялась не более чем в одной части, и возвращать список целых чисел, представляющих размер каждой части.

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]

Объяснение: Раздел равен "ababcbaca "," defgde "," hijhklij ".Это раздел, так что каждая буква появляется не более чем в одной части.

Раздел, такой как «ababcbacadefegde», «hijhklij», является неправильным, поскольку он разбивает S на меньшее количество частей.

Ниже приведен мой код для вышеуказанной проблемы:

class Solution {
public List<Integer> partitionLabels(String S) {

    char[] st = S.toCharArray();
    int k=0,c=0;
    List<Integer> res = new ArrayList<Integer> ();
    Set<Integer> visited = new HashSet<Integer> ();

    for(int i=0 ; i<st.length ; i++)
    {
        int idx = S.lastIndexOf(st[i]);
        if(visited.add(i) && idx>i && idx>k)
        {
            k = Math.max(k,idx);
            visited.add(k);

        }
        else if(i == k)
        {
            res.add(i-c+1);
            c=i+1;
            k++;
        }
    }

    return res;

}
}

Приведенный выше код работает и временная сложность указанного кода в O (n), поскольку он посещает каждый элемент один раз.

Но какова сложность пространства?Поскольку я использую массив Char, размер которого совпадает с размером String S и множеством, чей максимальный размер может быть размером строки St, это также O (n)?

Answer 1

Поскольку вы используете только одномерные массивы и списки, ваша сложность пространства равна O (n).

Но ваша временная сложность равна O (n²), потому что S.lastIndexOf(st[i]); - это O (n).

Если вы также хотели, чтобы время было O (n), вы должны предварительно обработать строку один раз (= O (n)), чтобы определить последнее вхождение каждого символа, f.i. с картой, чтобы сохранить время получения O (1).