Максимизируйте количество подстрок, чтобы ни одна подстрока не имела символов из другой подстроки

Question

Итак, мне недавно был задан интересный вопрос, связанный со строками и подстрокой. Все еще пытаюсь получить самый оптимальный ответ на это. Я предпочитаю ответ в Java, хотя любой псевдо-код / ​​язык также будет хорош.

Вопрос:

Мне дана строка S. Я должен разделить ее в максимальное количество подстрок (не подпоследовательность), так что ни одна из подстрок не имеет символа, который присутствует в другой подстроке.

Примеры:

1.
   S = "aaaabbbcd"
   Substrings = ["aaaa","bbb","c","d"]

2.
   S = "ababcccdde"
   Substrings = ["abab","ccc","dd","e"]

3.
   S = "aaabbcccddda"
   Substrings = ["aaabbcccddda"]

Буду очень рад, если смогу найти решение, которое лучше O(n^2)

Спасибо за помощь.

Answer 1

Это можно сделать за O (n) время.

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

Давайте использовать abbacacd как пример. Предположим, мы знаем первое и последнее вхождения каждого символа в строке.

01234567
abbacacd   (reading a at index 0)

- we know that our substring must be at least abbaca (last occurrence of a);
- the end of our substring will be the maximum between the last occurrence of 
  all the chars inside the own substring;
- we iterate through the substring:

012345     (we found b at index 1)
abbaca      substring_end = maximum(5, last occurrence of b = 2)
            substring_end = 5.

012345     (we found b at index 2)
abbaca      substring_end = maximum(5, last occurrence of b = 2)
            substring_end = 5.

012345     (we found a at index 3)
abbaca      substring_end = maximum(5, last occurrence of a = 5)
            substring_end = 5.

012345     (we found c at index 4)
abbaca      substring_end = maximum(5, last occurrence of c = 6)
            substring_end = 6.

0123456    (we found a at index 5)
abbacac     substring_end = maximum(6, last occurrence of a = 5)
            substring_end = 6.

0123456    (we found c at index 6)
abbacac     substring_end = maximum(6, last occurrence of c = 6)
            substring_end = 6. 

---END OF FIRST SUBSTRING---

01234567
abbacacd           [reading d]

- the first and last occurrence of d is the same index.
- d is an atomic substring.

Решение O (n):

#include <bits/stdc++.h>

using namespace std;

int main(){
    int pos[26][2];
    int index;
    memset(pos, -1, sizeof(pos));
    string s = "aaabbcccddda";

    for(int i = 0; i < s.size(); i++){
        index = s[i] - 'a';
        if(pos[index][0] == -1) pos[index][0] = i;
        pos[index][1] = i;
    }

    int substr_end;
    for(int i = 0; i < s.size(); i++){
        index = s[i] - 'a';
        if(pos[index][0] == pos[index][1]) cout<<s[i]<<endl;
        else{
            substr_end = pos[index][1];
            for(int j = i + 1; j < substr_end; j++){
                substr_end = max(substr_end, pos[s[j] - 'a'][1]);
            }
            cout<<s.substr(i, substr_end - i + 1)<<endl;
            i = substr_end;
        }
    }
}

Answer 2

Принятый ответ включает в себя некоторые ненужные сложности в реализации алгоритма. Очень просто разделить строки (как примеры, опубликованные рассматриваемым OP) на максимальное количество подстрок, так что ни одна подстрока не имеет символа, который присутствует в другой подстроке.

Алгоритм:
(допущение: входная строка является ненулевой строкой, имеющей 1 или более символов в пределах от 'a' до 'z' включительно)

1. Запись последней позиции каждого символа входной строки.
2. Предположим, первая конечная позиция подстроки равна 0.

3. Итерация по строке и для каждого символа во входной строке -

   a). Если последняя позиция текущего символа больше конечной позиции подстроки, чем обновить конечную позицию подстроки до последней позиции текущего символа.
   b). Добавить (или распечатать) текущую обработку символов как часть текущей подстроки.
   c). Если конечная позиция подстроки равна позиции текущей символьной обработки, то это конец уникальной подстроки, и со следующего символа начинается новая подстрока.

4. Повтор 3 до конца входной строки.

Реализация:

#include <stdio.h>
#include <string.h>

void unique_substr(const char * pst) {
    size_t ch_last_pos[26] = {0};
    size_t subst_end_pos = 0;
    size_t len = strlen(pst);

    printf ("%s -> ", pst);
    for (size_t i = 0; i < len; i++) {
        ch_last_pos[pst[i] - 'a'] = i;
    }

    for (size_t i = 0; i < len; i++) {
        size_t pos = ch_last_pos[pst[i] - 'a'];
        if (pos > subst_end_pos) {
            subst_end_pos = pos;
        }

        printf ("%c", pst[i]);

        if (subst_end_pos == i) {
            printf (" ");
        }
    }
    printf ("\n");
}

//Driver program

int main(void) {

    //base cases
    unique_substr ("b");
    unique_substr ("ab");

    //strings posted by OP in question
    unique_substr ("aaaabbbcd");
    unique_substr ("ababcccdde");
    unique_substr ("aaabbcccddda");

    return 0;
}

Вывод:

# ./a.out
b -> b 
ab -> a b 
aaaabbbcd -> aaaa bbb c d 
ababcccdde -> abab ccc dd e 
aaabbcccddda -> aaabbcccddda 

Answer 3

Вы можете сделать это за два прохода. 1-го числа вы определяете максимальный индекс каждого символа в строке. На втором вы отслеживаете максимальный индекс каждого встреченного символа. Если max равно текущему индексу, вы достигли конца уникальной подстроки.

Вот пример Java кода для иллюстрации:

char[] c = "aaaabbbcd".toCharArray();

int[] max = new int[26];        
for(int i=0; i<c.length; i++) max[c[i]-'a'] = i;;

for(int i=0, m=0, lm=0; i<c.length;)
  if((m = Math.max(m, max[c[i]-'a'])) == i++) 
    System.out.format("%s ", s.substring(lm, lm = i));

Вывод:

aaaa bbb c d 

И для других 2 строк:

abab ccc dd e 
aaabbcccddda