CareerCup

I think that if the maximum frequency is at most the total number of other characters + 1, then the arrangement exists. We can construct the solution by starting with the character with the maximum frequency and decrementing its counter, then adding the next different character with the maximum frequency and decrementing and so on. If many chars have the same frequency any one of them can be chosen. Keeping track only if that arrangement exists would be O(1) time and space for each character from the infinite sequence, while constructing the solution with the algorithm above would be O(n) time (the max-heap's size does not depend on the input size) and O(1) space.

@koustav, would you mind explaining your algo at a high level? I think your algo is creating max heap and simulating the arrangement?

The idea I had was to use min-heap. Basic idea is to count the frequencies of chars, then create create min heap based on those frequency. With the min heap, we would then check if the difference of the children with current is <= 1, else its not possible for such arrangement.

For example:

- input: "AAABBCCDEF" 
 - calculate frequency of each character:  [3,2,2,1,1,1]
 - create min heap: [1,2,1,3,2,1]
      1
     2 1
   3 2 1
- now for each node calculate Math.abs( (leftChild+rightChild) - current ) and return that value.
- At root node, the tree is arrangable only if the Math.abs( (leftChild+rightChild) - current )  <= 1

That seems like it would work, any thoughts? I'll test it out the idea in bit, but wondering if anyone had thoughts?

1. Keep count of each character.
2. Sort them in decreasing order based on there number of count.
3. Pick first two and start decrementing from both of them till one of them reaches to Zero.
4. Item which count is zero remove that and move to step 2 again.
If only one char left with any count then it's not possible.


Another Note:

In question input is:        "AAABBCCDEF"
Output is:                  "ABABCDCEF"
where output should be:     "ABABCACDEF"

static class HeapNode {
		char c;
		int count;

		public HeapNode(char c, int count) {
			this.c = c;
			this.count = count;
		}

		public char getC() {
			return c;
		}

		public void setC(char c) {
			this.c = c;
		}

		public int getCount() {
			return count;
		}

		public void setCount(int count) {
			this.count = count;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + c;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			HeapNode other = (HeapNode) obj;
			if (c != other.c)
				return false;
			return true;
		}

		@Override
		public String toString() {
			return "HeapNode [c=" + c + ", count=" + count + "]";
		}

	}

	public static String arrange(String str) {
		int count[] = new int[26];
		int max = Integer.MIN_VALUE;
		for (char c : str.toCharArray()) {
			count[c - 'a'] = count[c - 'a'] + 1;
			if (max < count[c - 'a']) {
				max = count[c - 'a'];
			}
		}
		if (max > ((str.length() / 2) + 1)) {
			System.out.println("Can't be done");
			return "";
		}
		char c = 'a';
		PriorityQueue<HeapNode> maxHeap = new PriorityQueue<HeapNode>(new Comparator<HeapNode>() {
			@Override
			public int compare(HeapNode o1, HeapNode o2) {
				return o2.count - o1.count;
			}
		});
		for (int i = 0; i < count.length; i++) {
			if (count[i] != 0) {
				HeapNode node = new HeapNode(c++, count[i]);
				maxHeap.add(node);
			}
		}
		StringBuffer sbf = new StringBuffer();
		HeapNode temp = null;
		while (!maxHeap.isEmpty()) {
			HeapNode node = maxHeap.poll();
			sbf.append(node.c);
			node.count--;
			if (temp != null && temp.count > 0) {
				maxHeap.add(temp);
			}
			temp = node;
		}
		return sbf.toString();
	}

	public static void main(String args[]) throws Exception {
		System.out.println(arrange("abcaabddddd"));
	}