字符串操作|竞争性编程

Question

我有一个大小为N的字符串(小写字母)，索引为1
现在我得到了Q个查询，每个查询由两个整数x，y组成
对于每个查询，我都必须打印从子字符串(x，y)(包括x，y在内)中删除的最小次数，以便子字符串具有相同频率的不同字符。

例如：考虑一个形成子字符串abbccd的查询，
现在其中的最小删除数为2(1b，1c)。

1<=N、 Q<=10^5

1<X<Y<N

我尝试了蛮力方法，对于每个查询，我计算字符的频率，然后通过将所有频率等同于最小频率来计算删除。

但我知道这种方法是错误的，也会导致TLE。有人能帮我吗？

我的代码：

import java.util.Arrays;
import java.util.Scanner;
public class q1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
in.nextLine();
String s = in.nextLine();
int x,y;
while(q>0){
x = in.nextInt();
y = in.nextInt();
String temp = s.substring(x-1, y);
char c[] = temp.toCharArray();
int count[] = new int[26];
//calculating the frequencies.
for (int i = 0; i < c.length; i++) {
count[c[i]-'a']++;
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < count.length; i++) {
if(count[i]!=0 && count[i]<min){
min = count[i];
}
}
int deletions = 0;
for (int i = 0; i < count.length; i++) {
if(count[i]!=0){
deletions += (count[i]-min);
}
}
System.out.println(deletions);

q--;
}
}
}

问题链接

Answer 1

这是我的解决方案，每个查询有O(26*26)个步骤。制作了一个累积频率阵列来存储每个字符的频率；第i"；字符串中的位置。

CCD_ 1是"0"的频率；a"；在从索引1到i(包括i)的字符串中
CCD_ 2是"；b"；在从索引1到i(包括i)的字符串中
依此类推，直到25为止；z"；。

现在在每个查询中，我们可以通过减去一个字符"y"的频率来计算子串x到y中每个字符的频率；i〃；直到"；x-1"；从相同字符的频率直到"0"；y"；即

freq[i] = dp[x-1][i] - dp[y][i];

现在，一旦我们有了子字符串中每个字符的频率，我们就可以迭代这些频率，并计算每个唯一字符的删除次数。

例如，如果我们有一个子串"；ddddbbacc">
freq of"；a"；是1
频率"；b"；是2
频率"；c"；是2
频率"；d"；是4

frequencies = [1, 2, 2, 4]
在第一次迭代中，我们试图使所有频率等于freq[0]，即1。
为此，我们从具有freq = 2的字符中删除一个字符，从具有freq = 4的字符中移除3个字符
这给了我们一个1+1+3 = 5的答案。

在第二次迭代中，我们试图使所有频率等于freq[1]，即2。
为此，我们从具有dp[i][0]0的字符中删除3个字符
并且我们还删除了freq < 2
的所有字符，这给了我们1+2 = 3的答案。

在最坏的情况下，每个查询需要26*26步。找到问题此处

import java.util.Arrays;
import java.util.Scanner;
import java.util.Collections;
import java.util.ArrayList;
class q1 {
static int[][] dp = new int[100005][27];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
in.nextLine();
String s = in.nextLine();

for (int i = 0; i < s.length(); i++){                   //O(N*26)
for (int j = 0; j < 26; j++)
dp[i+1][j] = dp[i][j];
dp[i+1][(int)(s.charAt(i))-(int)('a')]++;
}

int x,y;
while(q>0){                                             //O(Q*700)
x = in.nextInt();
y = in.nextInt();
int freq[] = new int[27];
for(int i = 0; i < 26; i++)                         //O(1)
freq[i] = dp[y][i] - dp[x-1][i];
ArrayList<Integer> f = new ArrayList<Integer>();
for(int i = 0; i < 26; i++)                         //O(1)
if(freq[i] != 0)
f.add(freq[i]);
Collections.sort(f);                                //O(26*log26)
int ans = s.length() + 1;
int drop = 0;
for(int i = 0; i < f.size(); i++){                  //O(26*26)
int currans = drop;
for(int j = i+1; j < f.size(); j++)
currans += (f.get(j)-f.get(i));
if (ans > currans)
ans = currans;
drop += f.get(i);
}
if (drop < ans)
ans = drop;
System.out.println(ans);
q--;
}
}
}