print all possible string without adjacent equal characters from repeated characters string

Question

Given a string as alphanumeric characters where some characters repeat in consecutive places, we have to scatter repeated characters to make them non-consecutive.

input: aaaabbbcdd11
Output: abababacd1d1 or any other valid combination.

If there is no such combination, then there should be no output.

This question was asked me in the interview. I am still unable to solve this algorithm. I am not sure whether this is right forum to ask or not. but I am very curios to know the right algorithm/data structure that can be used to solve this.

I tried to create a hash (map) to so that I can keep the count of all characters.

str = "aaaabbbcdd11"
hashChrs = {}
for item in list(str):
     if item in hashChrs:
         hashChrs[item] = hashChrs[item] + 1
     else:
         hashChrs[item] = 1
print hashChrs

{'a': 4, '1': 2, 'c': 1, 'b': 3, 'd': 2}

When the highest frequency characters count will be more than half of total characters then no output will be generated.

Now I am not able to print all the desired output using map

what did you try to do/how did you try to solve this? – depperm May 30 '17 at 18:19 — depperm, May 30 '17 at 18:19

score 3 · Accepted Answer · answered May 30 '17 at 18:34

It can be scattered if and only if there is no character which occurs more than ceiling(length of string/2) times. Can you see why it would be impossible to scatter a character if it occurred more than that? (Answer below.)

The maximal number of a character we can fit is obtained by fitting them in alternately, i.e. "abababa" gives the maximum number of instances of the letter "a" that can fit in 7 characters, 4; this number can be worked out using the formula ceiling(length of string/2).

Now, the algorithm is as follows: sort the characters by how often they appear in the string (so "abcdabcaba" would become "aaaabbbccd"), then use a reverse rail fence cipher with 2 rails; that is to say, split the sorted string in half (if it has even length, split it exactly in half; if not, split it such that the first half has one more character) and then to build up the final string, alternately take characters from each string, starting with the first. Thus, "aaaabbbccd" would become "ababacacbd". I'll leave it to you to prove that this works.

To do so, you may wish to consider what happens to blocks of characters of varying sizes under the reverse rail fence.

print all possible string without adjacent equal characters from repeated characters string

1 Answers1