Поиск минимальных пар из заданных входных данных ⇐ JAVA

[Anonymous]

У меня есть строка s длины n, состоящая всего из 3 символов 0, 1 и !, а также двух чисел, представленных как x и y
Теперь мне нужно заменить ! на 0 или 1
Затем подсчитать количество подпоследовательностей 01 произнесите count1, а также 10 произнесите count2
Теперь вычислите сумму = (x * count1) + (y * count2 )
Найдите минимально возможную сумму.
Вывод может быть большим, поэтому возвращайте результат по модулю 10^9 + 7 .
Пример:

Код: Выделить всё

s = "101!1", x = 2, y = 3

Result = 9

Объяснение:

Код: Выделить всё

case 1:

Replace '!' with '0' then we get "10101"
number of "01" subsequences are count1 = 3 at indices (1,2), (1,4), (3,4)
number of "10" subsequences are count2 = 3 at indices (0,1), (0,3), (2,3)

Sum =  (x * count1) + (y * count2) = 2*3 + 3*3 = 15

case 2:

Replace '!' with '1' then we get "10111"
number of "01" subsequences are count1 = 3 at indices (1,2), (1,3), (1,4)
number of "10" subsequences are count2 = 1 at indices (0,1)

Sum =  (x * count1) + (y * count2) = 2*3 + 3*1 = 9

Result min(15, 9) = 9

Другой пример:

Код: Выделить всё

n = 7, s = "!!!!!!!", x = 23, y = 47

Result = 0

Объяснение:

Код: Выделить всё

Replace '!' with '0' then we get "0000000"
number of "01" subsequences are count1 = 0
number of "10" subsequences are count2 = 0

Sum = 23 * 0 + 47 * 0 = 0

Replace '!' with '1' then we get "1111111"
number of "01" subsequences are count1 = 0
number of "10" subsequences are count2 = 0

Sum = 23 * 0 + 47 * 0

Result = min(0, 0) = 0

Ограничения:

Код: Выделить всё

`n` ranges from 1 to 10^5
values of x and y range is [0, 10^5]

Вот мой код:

Код: Выделить всё

public static void main(String[] args) {
System.out.println(solve("101!1",2,3));//9
System.out.println(solve("!!!!!!!",23,47));//0
}

static int solve(String s, int x, int y) {
long zero = 0, one = 0;
long count1 = 0, count2 = 0;
int mod = 1000_000_007;
for(char c : s.toCharArray()) {
if(c == '1') {
one = (one + 1 ) %mod;
count1 = (count1 + zero) % mod;
} else {
zero = (zero + 1) % mod;
count2 = (count2 + one) % mod;
}
}
long sum1 = ((count1 * x)%mod + (count2 * y) % mod)%mod;
zero = 0;
one = 0;
count1 = 0;
count2 = 0;
for(char c : s.toCharArray()) {
if(c == '1' || c == '!') {
one = (one + 1 ) %mod;
count1 = (count1 + zero) % mod;
} else {
zero = (zero + 1) % mod;
count2 = (count2 + one) % mod;
}
}
long sum2 = ((count1 * x)%mod + (count2 * y) % mod)%mod;
return (int) Math.min(sum1, sum2);
}

Этот вопрос я получил во время собеседования на хакерранке, мне удалось частично ответить, и с помощью моего приведенного выше кода было пройдено 13 тестовых случаев из 15.
Оставшиеся два тестовых примера не пройдены. с неправильным выводом, для этих двух тестовых случаев входная строка имеет длину 1 00 000, поэтому я не смог отладить, почему мой код не работает.
Каков правильный подход к решению проблемы? решить эту проблему.

Подробнее здесь: https://stackoverflow.com/questions/787 ... iven-input