Как найти номера действительной подстроки, используя алгоритм сложности времени O (n) - PullRequest
Новая
       16

Как найти номера действительной подстроки, используя алгоритм сложности времени O (n)

0 голосов
/ 07 июня 2018

, поэтому мне нужен метод java, который получает переменную типа String, переменную типа char и переменную типа int: 

public static int subStrMaxC(String s, char c, int k)

Так что идея этого метода состоит в проверке количества подстрокв строках s, которые начинаются и заканчиваются символом c и имеют максимум символов kc внутри них.при использовании временной сложности O (n) при n == s.length() добавлении документации API ниже: 

/**
     * Checks how many Sub-Strings are within a given String that starts and ends with a given character and also has that character inside the Sub-String maximum a given amount of times.
     * @param s the String to check for the Sub-String within.
     * @param c the character to check the Sub-String according to.
     * @param k the amount of time that the given character has to be within every Sub-String.
     * @return the number of the valid Sub-Strings.
     * @timeComplexity O(n) n - the String's (s) length.
     * @SpaceComplexity O(1)
     */

например: subStrMaxC ("abcabcabc", 'c', 1);должен вернуть 3, потому что допустимая подстрока: "cabc", "cabc", "cabcabc"

вот мой код, но он не возвращает правильных ответов: 

public static int subStrMaxC(String s, char c, int k) {
    int count = 0, toReturn = 0;
    for(int index = 0; index < s.length(); index++) {
        if(s.charAt(index) == c)
            count++;
    }

    while(k >= 0) {
        if(k == 0)
            return toReturn;
        else if(k % 2 == 0) {
            toReturn += count - (k + 1) - toReturn;
            k--;
        }
        else {
            toReturn += count / 2 - toReturn;
            k--;
        }
    }
    return toReturn;
}

Будетлюблю получать помощь!Спасибо!

1 Ответ

0 голосов
/ 07 июня 2018

Нам нужно сделать несколько наблюдений, чтобы решить эту проблему:

Предположим, что у нас самая длинная допустимая подстрока, которая заканчивается индексом ith, который содержит x символ c, с x <= kитак, он содержит x + 2 символ c.Мы можем сказать, что любая подстрока, которая заканчивается этим индексом ith и начинается с любого из первых x+1 символов, является допустимой подстрокой.

Итак, для каждого символа c в строке мыпросто нужно найти номер символа c (обозначается count), который стоит перед ним, если он больше k + 1, просто добавьте k + 1 к результату, в противном случае просто добавьте count.

Итак, вот псевдокод: 

int result = 0;
int count = 0;
for(int i = 0; i < s.length(); i++){
    if(s.charAt(i) == c){
       result += Integer.min(k + 1, count);
       count++;
    } 
}

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

Рабочая демонстрация: https://ideone.com/aUpxk5

...