Krdytkyu

Problem Statement

Given two strings s1 and s2, we want to visualize how different the two strings are. We will only take into account the lowercase letters (a to z). First let us count the frequency of each lowercase letters in s1 and s2.



  s1 = "A aaaa bb c" 



  s2 = "& aaa bbb c d" 



  s1 has 4 'a', 2 'b', 1 'c' 



  s2 has 3 'a', 3 'b', 1 'c', 1 'd' 



  So the maximum for 'a' in s1 and s2 is 4 from s1; the maximum for 'b' is 3 from s2. In the following we will not consider letters when the maximum of their occurrences is less than or equal to 1.

  We can resume the differences between s1 and s2 in the following string: "1:aaaa/2:bbb" where 1 in 1:aaaa stands for string s1 and aaaa because the maximum for a is 4. In the same manner 2:bbb stands for string s2 and bbb because the maximum for b is 3.

  The task is to produce a string in which each lowercase letters of s1 or s2 appears as many times as its maximum if this maximum is strictly greater than 1; these letters will be prefixed by the number of the string where they appear with their maximum value and :. If the maximum is in s1 as well as in s2 the prefix is =:. 



  In the result, substrings (a substring is for example 2:nnnnn or 1:hhh; it contains the prefix) will be in decreasing order of their length and when they have the same length sorted in ascending lexicographic order (letters and digits - more precisely sorted by codepoint); the different groups will be separated by '/'. See examples and "Example Tests". 

  Hopefully other examples can make this clearer. 

  s1 = "my&friend&Paul has heavy hats! &" 

  s2 = "my friend John has many many friends &" 

  mix(s1, s2) --> "2:nnnnn/1:aaaa/1:hhh/2:mmm/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss" 



  s1 = "mmmmm m nnnnn y&friend&Paul has heavy hats! &" 

  s2 = "my frie n d Joh n has ma n y ma n y frie n ds n&" 

  mix(s1, s2) --> "1:mmmmmm/=:nnnnnn/1:aaaa/1:hhh/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss" <br/>



  s1="Are the kids at home? aaaaa fffff" 

  s2="Yes they are here! aaaaa fffff" 

  mix(s1, s2) --> "=:aaaaaa/2:eeeee/=:fffff/1:tt/2:rr/=:hh" 

  Note for Swift, R, PowerShell 

  The prefix =: is replaced by E: 



  s1 = "mmmmm m nnnnn y&friend&Paul has heavy hats! &" 

  s2 = "my frie n d Joh n has ma n y ma n y frie n ds n&" 

  mix(s1, s2) --> "1:mmmmmm/E:nnnnnn/1:aaaa/1:hhh/2:yyy/2:dd/2:ff/2:ii/2:rr/E:ee/E:ss" 

Here's My Solution:

public class StringMixKata {



    private static final Set<Character> uniqueAlphabets = new LinkedHashSet<>();

    private static final String LOWER_CASE_ALPHABET_NEGATED_REGEX = "[^a-z]+";

    private static final String EQUALITY = "=";

    private static final String COLON = ":";

    private static final String FORWARD_SLASH = "/";

    private static final String EMPTY_STRING = "";

    private static final String EMPTY_CHARACTER = "";

    private static final int MINIMUM_FREQUENCY_REQUIRED = 2;





    private static String stringMix(String s1,String s2){

        s1 = removeAllCharactersExceptLowerCaseAlphabets(s1);

        s2 = removeAllCharactersExceptLowerCaseAlphabets(s2);

        Map<Character,Integer> s1CharacterFrequencyMap = calculateFrequencyForEachAlphabetAndAddEachAlphabetToSetOfUnique(s1);

        Map<Character,Integer> s2CharacterFrequencyMap = calculateFrequencyForEachAlphabetAndAddEachAlphabetToSetOfUnique(s2);

        List<AlphabetFrequencyAndOrigin> finalList  = createListOfFrequenciesForFinalString(s1CharacterFrequencyMap,s2CharacterFrequencyMap);

        return formatString(finalList);

    }



    private static String removeAllCharactersExceptLowerCaseAlphabets(final String input){

        return input.replaceAll(LOWER_CASE_ALPHABET_NEGATED_REGEX,EMPTY_STRING);

    }



    /**

     * Calculates the frequency of each character in the string and returns the frequencies

     * of the characters as a {@link Map} with the characters as the key and the frequency

     * as the value of the Map. This function also add each character to a {@link Set} of Unique

     * alphabets.

     * @param input

     * @return Map

     */

    private static Map<Character,Integer> calculateFrequencyForEachAlphabetAndAddEachAlphabetToSetOfUnique(final String input){

        Map<Character,Integer> alphabetFrequency = new HashMap<>();

        for (char alphabet: input.toCharArray()) {

            uniqueAlphabets.add(alphabet);

            if(alphabetFrequency.containsKey(alphabet)){

                int frequency = alphabetFrequency.get(alphabet)+1;

                alphabetFrequency.put(alphabet,frequency);

            }else{

                alphabetFrequency.put(alphabet,1);

            }

        }

        return alphabetFrequency;

    }



    /**

     * Creates a list of {@link AlphabetFrequencyAndOrigin} objects.

     * The final list contains the Alphabets of higher frequency with their origin.

     * This list contains only element for every alphabet. <br/>

     * For example if there is a character 'a'. Now one map has a frequency of 3 and the Other map has

     * a frequency of 4. So any entry will be added to the returning list with frequency of 4 with the origin

     * set as the latter one. Before returning the list this function will also sort the list based on the frequencies

     * of the alphabets. If the frequencies are same for two alphabets then the elements would be compared alphabetically.

     * @param s1CharacterFrequencyMap

     * @param s2CharacterFrequencyMap

     * @return List

     */

    private static List<AlphabetFrequencyAndOrigin> createListOfFrequenciesForFinalString(final Map<Character,Integer> s1CharacterFrequencyMap, final Map<Character,Integer> s2CharacterFrequencyMap){

        final List<AlphabetFrequencyAndOrigin> finalList = new LinkedList<>();

        for (Character alphabet: uniqueAlphabets) {

            if(bothTheMapsContainTheAlphabetWithSameFrequency(s1CharacterFrequencyMap,s2CharacterFrequencyMap,alphabet)){

                if(s1CharacterFrequencyMap.get(alphabet) < MINIMUM_FREQUENCY_REQUIRED) continue;

                finalList.add(new AlphabetFrequencyAndOrigin(null,alphabet,s1CharacterFrequencyMap.get(alphabet)));

            }

            if(bothTheMapsContainTheAlphabet(s1CharacterFrequencyMap,s2CharacterFrequencyMap,alphabet)){

                if(s1CharacterFrequencyMap.get(alphabet) < s2CharacterFrequencyMap.get(alphabet)){

                    finalList.add(new AlphabetFrequencyAndOrigin(2,alphabet,s2CharacterFrequencyMap.get(alphabet)));

                }

                if(s1CharacterFrequencyMap.get(alphabet) > s2CharacterFrequencyMap.get(alphabet)){

                    finalList.add(new AlphabetFrequencyAndOrigin(1,alphabet,s1CharacterFrequencyMap.get(alphabet)));

                }

            }else{

                if(s1CharacterFrequencyMap.get(alphabet)!=null && s1CharacterFrequencyMap.get(alphabet) >= MINIMUM_FREQUENCY_REQUIRED) finalList.add(new AlphabetFrequencyAndOrigin(1,alphabet,s1CharacterFrequencyMap.get(alphabet)));

                if(s2CharacterFrequencyMap.get(alphabet)!=null && s2CharacterFrequencyMap.get(alphabet) >= MINIMUM_FREQUENCY_REQUIRED) finalList.add(new AlphabetFrequencyAndOrigin(2,alphabet,s2CharacterFrequencyMap.get(alphabet)));

            }



        }

        Collections.sort(finalList);

        return finalList;

    }





    private static boolean bothTheMapsContainTheAlphabet(final Map<Character,Integer> s1, final Map<Character,Integer> s2, final char alphabet){

        return s1.containsKey(alphabet) && s2.containsKey(alphabet);

    }



    private static boolean bothTheMapsContainTheAlphabetWithSameFrequency(final Map<Character,Integer> s1, final Map<Character,Integer> s2, final char alphabet){

        return bothTheMapsContainTheAlphabet(s1,s2,alphabet) ? s1.get(alphabet).equals(s2.get(alphabet)) : Boolean.FALSE;

    }



    /**

     * Creates a string where each alphabet is denoted by the its origin ':' number of times the character is repeated. And

     * each character is joined by '/'. So an example would be : <br/>

     * <code>1:mmmmmm/=:nnnnnn/1:aaaa/1:hhh/2:yyy/2:dd/2:ff/2:ii/2:rr/=:ee/=:ss .</code> <br/>

     * <br/>

     * The equality character means the origin is null.

     * @param finalSet

     * @return

     */

    private static String formatString(final List<AlphabetFrequencyAndOrigin> finalSet){

        StringBuilder builder = new StringBuilder();

        for (AlphabetFrequencyAndOrigin item: finalSet) {

            if(item.getOrigin()==null) builder.append(EQUALITY);

            else builder.append(item.getOrigin());

            builder.append(COLON);

            builder.append(repeatAlphabet(item.getAlphabet(),item.getFrequency()));

            builder.append(FORWARD_SLASH);

        }

        builder = removeTheLastForwardSlash(builder);

        return builder.toString();

    }



    /**

     * This method returns a string "aaaa" if you pass 'a' as the character and 4 as the frequency. This method

     * is a implementation of the multiplication operation on the characters. Copied the implementation from

     * <a href="https://stackoverflow.com/questions/1235179/simple-way-to-repeat-a-string-in-java">

     *   Simple way to repeat a String in java  </a> . This is really clever.

     * @param alphabet

     * @param frequency

     * @return String

     */

    private static String repeatAlphabet(final char alphabet,final int frequency){

        return new String(new char[frequency]).replace(EMPTY_CHARACTER, String.valueOf(alphabet));

    }



    private static StringBuilder removeTheLastForwardSlash(final StringBuilder builder){

        return builder.replace(builder.lastIndexOf(FORWARD_SLASH),builder.length(),EMPTY_STRING);

    }



};



/**

 * A class that holds the String number to which the alphabet belongs to and the frequency of the alphabet.

 * This is just container class that also helps in sorting by implementing the {@link Comparable} interface.

 * If the origin is set as null then it is assumed that the alphabet is present in both the string under comparision.

 *

 */

class AlphabetFrequencyAndOrigin implements Comparable<AlphabetFrequencyAndOrigin>{



    private final Integer origin;



    private final Character alphabet;



    private final Integer frequency;



    public AlphabetFrequencyAndOrigin(Integer origin, Character alphabet, Integer frequency) {

        this.origin = origin;

        this.alphabet = alphabet;

        this.frequency = frequency;

    }



    public Integer getOrigin() {

        return origin;

    }



    public Character getAlphabet() {

        return alphabet;

    }



    public Integer getFrequency() {

        return frequency;

    }



    @Override

    public int compareTo(AlphabetFrequencyAndOrigin o) {

        if(origin ==null && o.getOrigin()==null && frequency.compareTo(o.getFrequency())==0) return alphabet.compareTo(o.getAlphabet());

        return frequency.compareTo(o.getFrequency())==0 ? alphabet.compareTo(o.getAlphabet()) : o.getFrequency().compareTo(frequency);

    }



}

I programmed the solution in Java 7. The reason I did that is because I'm having a hard time understanding streams and supplier,consumer concepts in Java 8 (Don't Know why Java is becoming a functional programming language). I know the solution can be improved drastically in java 8.

The order of the strings in the output would not match for some sample inputs provided. The author specifically said lexicographic order and I wrote the compareTo function in that fashion only. Am I doing something wrong here Or have I misunderstood something?

Is there any room for improvements here? Is there anything wrong with my approach?. Need your opinions.