Given a string, find the longest substring with the same number of vowels and consonants?

Question

Given a string, find the longest substring with the same number of vowels and consonants.

CLARIFICATION: I'm not sure if we can generate a new line, or should the substring be part of the original line? As long as I have it

Code snippet:

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); 

EDIT I got a counter, but how do I create a substring?

Answer 1

This can be solved in O (n) time and space using the "net" values ​​computed by this answer in combination with the following observation:

• The substring s [i .. j] has the same number of consonants and vowels if and only if net [1 .. i-1] = net [1, j], where net [i .. j] is the sum " pure "values ​​(1 for the vowel, -1 for the consonant) for each character between positions i and j inclusively.

To verify this, note that the condition indicating that the substring s [i .. j] is the kind we are looking for is that

 net[i .. j] = 0. 

Adding a network [1 .. i-1] to both sides of this equation gives

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

with LHS and then simplifying only

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

Algorithm

This means that we can create a table containing two records (visible first position and last position) for each possible different value that we could get when we calculate the current amount of pure values. This current total amount can have a value of -n (if each character is consonant) or higher than n (if each character is a vowel), so the total is no more than 2n + 1 of such sums, so we will need a lot in our table lines. Then we go through the line from left to right, calculating the current total network value and update the pair in the table that corresponds to the current total, noticing when this update creates a new substring of maximum length. In pseudocode with zero array indices and using separate arrays to store elements in each pair:

• Create 2 arrays of length 2n + 1, first [] and last [], initially containing all -2s, except for the first [n], which is -1. (You must use -2 as a sentinel, since -1 is actually a valid value!)
• Set bestFirst = bestLast = bestLen = -1.
• Set the current value t = n. (n "means" 0, using this offset means that we can use the current value directly as a non-negative index in arrays without having to repeatedly add the offset to it.)
• For i from 0 to n-1:
  • If s [i] is a vowel, increment t; otherwise, decrease t.
  • If the first [t] is -2:
    • Set first [t] = i.
  • Otherwise:
    • Set the last [t] = i.
    • If the last [t] is the first [t]> bestLen:
      • Set bestLen = last [t] - first [t].
      • Set bestFirst = first [t] + 1.
      • Set bestLast = last [t].

The maximum length range will be returned (bestFirst, bestLast), or if no such range exists, these variables will be -1.

I remember that I saw this solution, or very similar to it, somewhere in SO some time ago - if anyone can find it, I will be happy to contact him.

Answer 2

To find the longest substring, where the number of consonants and vowels is equal, start finding the substrings at the longest length and gradually reduce the length needed until you find the substring that matches the criteria.

This will allow you to complete the job shortly.

 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 3

Here is an updated version of my original answer that works in O(n^2) time. He accomplishes this using a trick, namely tracking one variable (called a "network"), which tracks the difference between the number of vowels and consonants. When this number is zero, this substring is balanced.

It takes O(n^2) to iterate over each possible substring in the worst case, but it does not take extra time to check each substring for strings and vowels, because it supports updating net with each new step, select a substring. Therefore, it reduces complexity from O(n^3) to 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 4

I think this may be the solution for your task (for a not too long input line):

 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

Well, the requirements here are very vague. He does not mention whether numbers or other keys are included in the input. I assumed the initial zero index, since at this point the samples are equal.

  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."); }