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 am unsure, whether we can generate a new string, or the substring has to be part of the original string? So far I have this,

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 the count working, 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:

• A 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 of the "net" values (1 for a vowel, -1 for a consonant) for each character between positions i and j, inclusive.

To see this, observe that the condition that tells us that a substring s[i .. j] is the kind we're looking for is that

net[i .. j] = 0.

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

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

with the LHS then simplifying to just

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

Algorithm

That means that we can create a table containing two entries (first position seen and last position seen) for each possible distinct value that we could get as we calculate a running sum of net values. This running total could range as low as -n (if every character is a consonant) or as high as n (if every character is a vowel), so there are at most 2n+1 distinct such sums in total, so we'll need that many rows in our table. We then march through the string from left to right calculating a running total net value, and updating the pair in the table that corresponds to the current running total, noticing whenever this update produces a new, maximum-length substring. In pseudocode, with zero-based array indices and using separate arrays to hold the elements in each pair:

1. Create 2 arrays of length 2n+1, first[] and last[], initially containing all -2s, except for first[n] which is -1. (Need to use -2 as a sentinel since -1 is actually a valid value!)
2. Set bestFirst = bestLast = bestLen = -1.
3. Set the running total t = n. (n "means" 0; using this bias just means we can use the running total directly as a nonnegative-valued index into the arrays without having to repeatedly add an offset to it.)
4. For i from 0 to n-1:
   • If s[i] is a vowel, increment t, otherwise decrement t.
   • If first[t] is -2:
     • Set first[t] = i.
   • Otherwise:
     • Set last[t] = i.
     • If last[t] - first[t] > bestLen:
       • Set bestLen = last[t] - first[t].
       • Set bestFirst = first[t] + 1.
       • Set bestLast = last[t].

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

I remember seeing this solution, or one very similar to it, somewhere on SO a while back -- if anyone can find it, I'll gladly link to it.

Answer 2

Here is an updated version of my original answer which runs in O(n^2) time. It achieves this by employing a trick, namely keeping track of a single variable (called 'net') which tracks the difference between the number of vowels and consonants. When this number is zero, a given substring is balanced.

It takes O(n^2) to iterate over every possible substring in the worst case, but it doesn't take any additional time check each substring for strings and vowels, because it keeps the net up to date with each new step to choose a substring. Hence, it reduces the 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 3

To find the longest substring where the number of consonants and vowels are equal, start finding substrings at the largest length, and steadily decrease the length needed until you find a substring that matches the criteria.

This will allow you to short-circuit the operation.

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