How to transform a string such that it only contai

Question

I was asked this question in an interview. We have a string s (all lowercase characters) from which we need to make a new string p such that :

• The total number of a's in the string should be equal or greater than the given value of an int variable a.
• The total number of e's in the string should be equal or greater than the given value of an int variable e.
• The total number of i's in the string should be equal or greater than the given value of an int variable i.
• The total number of o's in the string should be equal or greater than the given value of an int variable o.
• The total number of u's in the string should be equal or greater than the given value of an int variable u.

Constraint was the in order to get the resultant string, we can replace any character with any other lower case character. We can do this any number of times but each replacement has a cost associated with it. the cost of replacing c1 with c2 is the absolute difference of ASCII value of c1 and c2. For eg. replacing b with e has a cost 3 and c with a has a cost 2.

We need to find the minimum cost of converting s into p. Given is:

• String s
• Five ints - a, e, i, o, u

My approach was to first sort the string, then decrease the given value of given int's each time we encounter the respective character, and then whichever given variable is greater than 0, we'll start from the beginning of the string and ig teh char is not a vowel, we'll calculate the cost of replacing it with the vowel of which corresponding variable is greater than zero and decrease it. It doesn't seem to work out. Please let me know your approach to solve it. If any information is obscure, let me know in comments. Thanks

here's my code:

public class VowelCount {
    static int minCount(String s, int a, int e, int i, int o, int u) {
        char[] array = s.toCharArray();
        List<Character> list = new ArrayList<>();
        list.add('a');
        list.add('e');
        list.add('i');
        list.add('o');
        list.add('u');

        Arrays.sort(array);

        for (int j = 0; j < s.length(); j++) {
            if (s.charAt(j) == 'a' && a > 0) {
                a--;
            }
            else if (s.charAt(j) == 'e' && a > 0) {
                e--;
            }
            else if (s.charAt(j) == 'i' && a > 0) {
                i--;
            }
            else if (s.charAt(j) == 'o' && a > 0) {
                o--;
            }
            else if (s.charAt(j) == 'u' && a > 0) {
                u--;
            }
        }
        int count =0;
        for (int j = 0; j < array.length; j++) {
            int count1=0, count2=0, count3=0, count4=0, count5=0, semicount1=0, semicount2=0, fincount=0;
            if (!list.contains(array[j])) {
                if (a > 0) {
                    int c1 =(int) array[j];
                    int c2 = (int) 'a';
                    count1 = Math.abs(c1-c2);
                    a--;
                }
                if (e > 0) {
                    int c1 =(int) array[j];
                    int c2 = (int) 'e';
                    count1 = Math.abs(c1-c2);
                    e--;
                }
                if (i > 0) {
                    int c1 =(int) array[j];
                    int c2 = (int) 'i';
                    count1 = Math.abs(c1-c2);
                    i--;
                }
                if (o > 0) {
                    int c1 =(int) array[j];
                    int c2 = (int) 'o';
                    count1 = Math.abs(c1-c2);
                    o--;
                }
                if (u > 0) {
                    int c1 =(int) array[j];
                    int c2 = (int) 'u';
                    count1 = Math.abs(c1-c2);
                    u--;
                }
                if (count1!=0 && count2!=0) {
                    semicount1 = Math.min(count1, count2);
                } else if (count1 == 0) {
                    semicount1 = count2;
                } else if (count2 == 0) {
                    semicount1 = count1;
                }
                if (count3 != 0 && count4 != 0) {
                    semicount2 = Math.min(count3, count4);
                } else if (count3 == 0) {
                    semicount2 = count4;
                } else if (count4 == 0) {
                    semicount2 = count3;
                }
                System.out.println("adding to count");
                fincount = Math.min(semicount1, semicount2);
                if (count5 != 0) {
                    count+= Math.min(count5, fincount);
                } else count+= fincount;

            }
        }
        System.out.println(count);
        return count;
    }

    public static void main(String[] args) {
        minCount("beiou", 1, 1, 1, 1 ,1);
    }
}

Answer 1

I'm assuming that the sum of a, b, c, d and e is at most s.length.

This problem can be solved in linear time. Before solving the problem, lets consider three scenarios:

• s = "bc", a = 1, e = 1, best p = "ae", optimal cost = 1 + 2
• s = "dj", a = 1, e = 1, best p = "ae", optimal cost = 3 + 5
• s = "fj", a = 1, e = 1, best p = "ae", optimal cost = 5 + 5

We can think the characters as points in number line. In the first scenario, the consonants lie between the vowels. In the second one, on consonant lie between the vowels and other one is outside. In the third example, both of them are outside. And we can see that, it is always better to choose the vowel with lower ASCII key at first and grab the cheapest constant for it.

So, now the approach would be, to convert all the constant to 'a' that we need, in cheapest cost. Then go for b, then c and so on.

EDIT: One particular case I've missed is that, if we've two options to choose from with same cost. Which one should we choose? The answer is to choose the one with lower ASCII value. Thanks to Tushar Makkar for pointing it out.