我在思考以下问题:
给定一个字符串S,让第i个子串的长度为li,第i个子串的出现次数为oi。打印出使li*oi最大的子串。
我对这个问题有一个O(n3)的解决方案(暴力解法),其中我生成所有子串并找到价值最大的子串。我的代码如下:
我对这个问题有一个O(n3)的解决方案(暴力解法),其中我生成所有子串并找到价值最大的子串。我的代码如下:
public static void solve(String S) {
long max = Integer.MIN_VALUE;
String res = "";
for (int i = 0; i < S.length(); i++) {
for (int j = 1; j <= S.length() - i; j++) {
String s = S.substring(i, i + j);
int o = countOccurrences(S, s);
long p = (long) o * (long) s.length();
if (max < p) {
max = p;
res = s;
}
}
}
System.out.println(res);
}
countOccurrences() 方法需要 O(n) 时间。我想知道是否有更有效的方法来实现这个功能。