[Java] permutation with duplicates

Question

I am following Cracking The Coding Interview section 8.8: permutation with duplicates. But it seems that my outcome is incorrect. Could you spot where the bug is?

Also, in the recursion part of the printPerms method, after the recursive line, what does map.put(c, count); do? I thought that we need to decrement the count for each character until it becomes zero, so I don't get why we restore the count.

import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;

public class PermWithDups {
    public static void main(String[] args) {
        printPerms("Hello");

    }

    static ArrayList<String> printPerms(String s) {
        ArrayList<String> result = new ArrayList<String>();
        HashMap<Character, Integer> map = buildFreqTable(s);
        printPerms(map, "H", s.length() - 1, result);

        System.out.println(Arrays.toString(result.toArray()));



        return result;
    }

    static void printPerms(HashMap<Character, Integer> map, String prefix, 
                    int remaining, ArrayList<String> result) {
        // Base Case for Recursion
        if (remaining == 0) {
            result.add(prefix);
            return;
        }

        // Recursion
        for (Character c : map.keySet()) {
            int count = map.get(c);
            if (count > 0) {
                map.put(c, count - 1);
                printPerms(map, prefix + c, remaining - 1, result);
                map.put(c, count);
            }
        }
    }

    static HashMap<Character, Integer> buildFreqTable(String s) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (char c : s.toCharArray()) {

            if (!map.containsKey(c)) {
                map.put(c, 0);
            }
            map.put(c, map.get(c) + 1);

        }
        return map;
    }

}

Answer 1 · 2016-11-10T23:51:18Z

November 10, 2016 11:51pm

I don't know if you're suppose to find all permutations of the letters or only the permutations starting with 'H', but the issue is where you start the top call of the recursion. Either you need to start with in empty string or you forgot remove the starting letter(s) from the frequency table.

It looks like map.put(c, count); is there to unwind the changes to the frequency table as the recursion backs out so the level above it can move on to the next character choice. Otherwise, if you only decremented you'd only get one permutation and the rest would be skipped over.

Welcome to the Treehouse Community

Looking to learn something new?

Derek Derek

Derek Derek

[Java] permutation with duplicates

1 Answer

Seth Kroger

Seth Kroger