给定一个字符串，找到具有相同元音和辅音数量的最长子字符串？

给定一个字符串，找到具有相同元音和辅音数量的最长子字符串。

澄清：我不确定，我们是否可以生成一个新字符串，或者子字符串必须是原始字符串的一部分？ 到目前为止我有这个，

代码片段：

Scanner scanner = new Scanner(System.in); String string = new String(scanner.next()); int lengthOfString = string.length(); int vowelCount = 0; int consCount = 0; for (int i = 0; i < lengthOfString; i++) { if (string.charAt(i) == 'u' || string.charAt(i) == 'e' || string.charAt(i) == 'i' || string.charAt(i) == 'o' || string.charAt(i) == 'a' ) { vowelCount++; } else { consCount++; } } System.out.println(vowelCount); 

编辑我得到了计数工作，但我如何创建子字符串？

Answer 1

这可以使用此答案计算的“净”值结合以下观察在O（n）时间和空间中求解：

• 当且仅当net [1 .. i-1] = net [1 .. j]时，子串s [i … j]具有相同数量的辅音和元音，其中net [i … j]是总和位置i和j之间的每个字符的“净”值（1表示元音，-1表示辅音）。

要看到这一点，请注意告诉我们子串s [i .. j]是我们正在寻找的那种情况是

 net[i .. j] = 0. 

将net [1 .. i-1]添加到此等式的两边给出

 net[1 .. i-1] + net[i .. j] = net[1 .. i-1] 

与LHS然后简化到公正

 net[1 .. j] = net[1 .. i-1] 

算法

这意味着我们可以创建一个包含两个条目的表（第一个看到的位置和看到的最后一个位置），我们可以在计算净值的运行总和时获得每个可能的不同值。 这个运行总数的范围可以低至-n（如果每个字符是辅音）或高至n（如果每个字符都是元音），那么总共最多有2n + 1个不同的总和，所以我们将在我们的表中需要很多行。 然后，我们从左到右遍历字符串，计算运行的总净值，并更新表中与当前运行总计相对应的对，注意每当此更新产生新的最大长度子字符串时。 在伪代码中，使用从零开始的数组索引并使用单独的数组来保存每对中的元素：

1. 创建2个长度为2n + 1，first []和last []的数组，最初包含所有-2，除了first [n]为-1。 （需要使用-2作为哨兵，因为-1实际上是一个有效值！）
2. 设置bestFirst = bestLast = bestLen = -1。
3. 设置运行总数t = n。 （n“表示”0;使用此偏差意味着我们可以将运行总计直接用作数组中的非负值索引，而不必重复添加偏移量。）
4. 对于从0到n-1的i：
   • 如果s [i]是元音，则递增t，否则递减t。
   • 如果first [t]是-2：
     • 首先设置[t] = i。
   • 除此以外：
     • 设置last [t] = i。
     • 如果last [t] – first [t]> bestLen：
       • 设置bestLen = last [t] – first [t]。
       • 设置bestFirst = first [t] + 1。
       • 设置bestLast = last [t]。

最大长度范围将在（bestFirst，bestLast）中返回，或者如果不存在这样的范围，则这些变量都将为-1。

我记得看到这个解决方案，或一个非常相似的解决方案，在某个地方的某个地方 – 如果有人能找到它，我很乐意链接到它。

Answer 2

这是我的原始答案的更新版本，在O(n^2)时间内运行。 它通过采用一种技巧来实现这一点，即跟踪单个变量（称为“网络”），该变量跟踪元音和辅音数量之间的差异 。 当此数字为零时，给定的子字符串是平衡的。

在最坏的情况下，需要O(n^2)迭代每个可能的子字符串，但它不需要任何额外的时间检查字符串和元音的每个子字符串，因为它使每个新步骤保持最新的选择一个子串。 因此，它将复杂度从O(n^3)到O(n^2) 。

 public String findLongestSubstring(String input) { String longest = ""; for (int window = inputz.length(); window >=2; --window) { String substr = input.substring(0, window); String consonants = input.substring(0, window).toLowerCase() .replaceAll("[aeiou]", ""); int vowelCount = input.substring(0, window).length() - consonants.length(); int consonantCount = consonants.length(); int net = vowelCount - consonantCount; for (int i=window; i <= input.length(); ++i) { if (net == 0) { longest = input.substring(i-window, i); return longest; } // no-op for last window if (i == input.length()) break; // update tally by removing high character if ("aeiou".indexOf(input.charAt(i)) != -1) { ++net; } else { --net; } // update tally by adding low character if ("aeiou".indexOf(input.charAt(i-window)) != -1) { --net; } else { ++net; } } } return longest; } 

Answer 3

要找到辅音和元音数相等的最长子字符串，请开始查找最大长度的子字符串，并稳定地减少所需的长度，直到找到符合条件的子字符串。

这将允许您短路操作。

 public static String findLongestSubstring(String str) { for (int len = str.length(); len >= 2; len--) { for (int i = 0; i <= str.length() - len; i++) { String substr = str.substring(i, i + len); int vowels = countVowels(substr); int consonants = len - vowels; if (vowels == consonants) { return substr; } } } return ""; } private static int countVowels(String str) { return str.replaceAll("[^AEIOUaeiou]+", "").length(); } 

Answer 4

我认为这可能是你的任务的决定（不是太长的输入字符串）：

 import org.junit.Test; /** * Created by smv on 19/09/16. */ public class MainTest { public static boolean isVowel(char c) { return "AEIOUaeiou".indexOf(c) != -1; } public int getVowelCount(String str) { int res = 0; for(int i=0; i < str.length(); i++){ if(isVowel(str.charAt(i))) { res++; } } return res; } public int getConsonantCount(String str) { int res = 0; for(int i=0; i < str.length(); i++){ if(!isVowel(str.charAt(i))) { res++; } } return res; } @Test public void run() throws Exception { String string = "aasdaasggsertcwevwertwe"; int lengthOfString = string.length(); String maxSub = ""; int maxSubLength = 0; // find all substrings of given string for( int c = 0 ; c < lengthOfString ; c++ ) { for( int i = 1 ; i <= lengthOfString - c ; i++ ) { String sub = string.substring(c, c+i); // comparing count vowels and consonants if (getVowelCount(sub) == getConsonantCount(sub)) { if (sub.length() > maxSubLength) { maxSub = sub; maxSubLength = sub.length(); } } } } System.out.println(maxSub); } } 

Answer 5

当然，这里的要求非常模糊。 它没有提到输入中是否包含数字或其他键。 我假设起始指数为零，因为计数在该点相等。

  Scanner scanner = new Scanner(System.in); String string = new String(scanner.next()); int lengthOfString = string.length(); int vowelCount = 0; int consCount = 0; int maxIndex = -1; for(int i = 0; i < lengthOfString; i++) { System.out.println("Char: " + string.charAt(i)); if(string.charAt(i) == 'u' || string.charAt(i) == 'e' || string.charAt(i) == 'i' || string.charAt(i) == 'o' || string.charAt(i) == 'a') { vowelCount++; } else { consCount++; } if(vowelCount == consCount) { System.out.println("count equal with: " + string.substring(0, (i + 1))); maxIndex = i + 1; } } if(maxIndex > 0) { System.out.println("Longest sub string with equal count of vowels and consonants is: " + string.substring(0, maxIndex)); } else { System.out.println("No substring existed with equal count of vowels and consonants."); }