Создать подстроку с помощью цикла

Question

Мне дана строка, из которой я должен найти подстроки, которые удовлетворяют следующим условиям

• все символы в подстроке одинаковы. Например: aa, bbb, cccc.

• все символы, кроме среднего, должны быть одинаковыми. например: aba, bbabb, et c.

Я сделал al go что-то вроде этого

Я клюю строку, используя два цикла 1-го l oop содержит первый символ, а второй l oop проходит через строку.

Затем я отправляю подстроку в vet (), чтобы увидеть, содержит ли подстрока меньше или равно двум символам. Если подстрока содержит два символа, тогда я проверяю, является ли ее палиндромом

public static int reverse(String s)
    {
        String wrd="";
        for(int i = s.length()-1 ;i>=0;i--)
            wrd = wrd + s.charAt(i);

        if(s.equals(wrd))
            return 1;
        else
            return 0;

    }

    public static boolean vet(String s)
    {
        HashSet<Character> hs = new HashSet<>();
        for(char c : s.toCharArray())
        {
            hs.add(c);
        }
        if(hs.size() <= 2)
            return true;
        else
            return false;
    }

    static long substrCount(int n, String s) {
        List<String> al = new ArrayList<>();

        for(int i=0;i<s.length();i++)
        {
            for(int j=i;j<s.length();j++)
            {
                        if(vet(s.substring(i,j+1)))
                        {
                            if(reverse(s.substring(i,j+1)) == 1)
                                al.add(s.substring(i,j+1));
                        }

            }
        }
        return al.size();
    }

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

Я подозреваю, что l oop, который разбивает строку и создает подстроку в substrCount (), вызывает сложность времени, так как имеет вложенные циклы.

Пожалуйста, просмотрите этот код и предоставьте лучший способ разбить строку или, если сложность возрастает из-за какого-то другого раздела, дайте мне знать.

ссылка: https://www.hackerrank.com/challenges/special-palindrome-again/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=strings

Answer 1

• Вы можете собирать значения с левой и правой стороны строки в 2 отдельных массива.
• Теперь мы собираем значения таким образом, если предыдущий символ равен текущему символу, увеличиваем счет на 1, в противном случае устанавливаем его равным 1.

Пример:

a  a  b  a  a  c  a  a

1  2  1  1  2  1  1  2 // left to right
2  1  1  2  1  1  2  1 // right to left

• Для строк, в которых все символы равны, мы просто собираем их все во время итерации.

• Для строк со всеми равными, кроме среднего символа, вы можете использовать приведенную выше таблицу и собирать строки, как показано ниже:

Псевдокод:

if(str.charAt(i-1) == str.charAt(i+1)){ // you will add checks for boundaries
    int min_count = Math.min(left[i-1],right[i+1]);
    for(int j=min_count;j>=1;--j){
        set.add(str.substring(i-j,i+j+1));
    }
}

Обновление:

Ниже мое принятое решение.

static long substrCount(int n, String s) {
    long cnt = 0;
    int[] left  = new int[n];
    int[] right = new int[n];
    int len = s.length();
    for(int i=0;i<len;++i){
        left[i] = 1;
        if(i > 0 && s.charAt(i) == s.charAt(i-1)) left[i] += left[i-1];
    }

    for(int i=len-1;i>=0;--i){
        right[i] = 1;
        if(i < len-1 && s.charAt(i) == s.charAt(i+1)) right[i] += right[i+1];
    }

    for(int i=len-1;i>=0;--i){
        if(i == 0 || i == len-1) cnt += right[i];
        else{
            if(s.charAt(i-1) == s.charAt(i+1) && s.charAt(i-1) != s.charAt(i)){
                cnt += Math.min(left[i-1],right[i+1]) + 1;
            }else if(s.charAt(i) == s.charAt(i+1)) cnt += right[i];
            else cnt++;
        }
    }

    return cnt;
}

Алгоритм:

• Алгоритм такой же, как объяснено выше, с несколькими дополнительными вещами.
• Если символ находится на границе, скажем 0 или len-1, мы просто смотрим на right[i] для подсчета строк, потому что у нас здесь нет left.

• Если символ находится внутри этой границы, мы делаем проверки следующим образом:

  • Если предыдущий символ равен следующему, мы проверяем, не совпадает ли предыдущий символ с текущим. Мы делаем это потому, что мы хотим избежать будущего добавления строк на самой текущей итерации (скажем, для строк типа aaaaa, где мы находимся в середине a).
  • Второе условие говорит s.charAt(i) == s.charAt(i+1), это означает, что у нас снова есть строки типа aaa, и мы на первом a. Поэтому мы просто добавляем right[i], чтобы указать добавление строк, таких как a, aa, aaa).
  • Третий означает cnt++, означающее добавление отдельного символа.

• Вы можете сделать несколько оптимизаций, например, полностью избегая right array et c, но я оставлю это вам в качестве упражнения.

• Сложность времени : O (n) , сложность пространства: O (n)

Answer 2

Текущее время выполнения решения - O (n ^ 4). Вы можете уменьшить его до O (n ^ 2logn), удалив количество символов в подстроках и оптимизировав часть проверки палиндрома.

Для этого вам нужно предварительно вычислить массив, скажем "counter", где каждая позиция массива «counter» указывает количество различных символов от начального индекса до этой позиции.

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

ОБНОВЛЕНИЕ! Позвольте мне объяснить на примере:

Предположим, строка "aaabaaa". Таким образом, массив счетчиков будет = [1, 1, 1, 2, 2, 2, 2]; Теперь давайте предположим, что в течение определенного c времени, внешнее значение для циклов i = 1 и внутреннее значение для циклов j = 5; поэтому подстрока "aabaa". Теперь, чтобы найти количество символов в подстроке с помощью следующего кода:

noOfDifferentCharacter = counter[j] - counter[i-1] + 1

Если noOfDifferentCharacter равен 1, тогда нет необходимости проверять палиндром. Если noOfDifferentCharacter равно 2, как в нашем случае, нам нужно проверить, является ли подстрока палиндромом. Чтобы проверить, является ли подстрока палиндромной, необходимо выполнить двоичный поиск в массиве счетчиков от индекса i до j, чтобы проверить позицию, где значение больше, чем его предыдущий индекс. В нашем случае позиция равна 3, тогда вам просто нужно проверить, является ли позиция средней позицией подстроки. Обратите внимание, что массив счетчиков отсортирован.

Надеюсь, это поможет. Дай мне знать, если не поймешь ни одного шага. Удачного кодирования!