kojino
BAN USERSorry the last post was for a different problem. Here's the working solution in Python.
result = []
def findStrings(n):
if n == 0:
return
if n == 1:
result = ['a','b','c']
# initalize result list and two counts
current_string = ""
count_b = 0
count_c_seq = 0
# throw the values into the recusion
findStringsHelper(current_string,count_b,count_c_seq,n)
return
def findStringsHelper(current_string,count_b,count_c_seq,n):
if len(current_string) >= n:
result.append(current_string)
else:
findStringsHelper(current_string+"a",count_b,0,n)
if count_b == 0:
findStringsHelper(current_string+"b",count_b+1,0,n)
if count_c_seq < 2:
findStringsHelper(current_string+"c",count_b,count_c_seq+1,n)
findStrings(2)
print result
print len(result)
A working Python solution.
def longest_palindrome(string):
# count how many times each char shows up
count = {}
for char in string:
if char in count:
count[char] += 1
else:
count[char] = 1
# if there are multiple odds, leave only one odd
odd_appeared = False
odd_char = ""
for key in count:
if count[key] % 2 == 1:
if odd_appeared:
count[key] -= 1
else:
odd_appeared = True
odd_char = key
# go through the dictionary and reconstruct the palindrome string
palindrome = ""
for key in count:
chars = count[key]/2 * key
palindrome = palindrome + chars
palindrome = chars + palindrome
if odd_appeared:
n = len(palindrome)
palindrome = palindrome[:n/2] + odd_char + palindrome[n/2:]
return palindrome
print longest_palindrome('ttaatta')
print longest_palindrome('abc')
print longest_palindrome('aha')
print longest_palindrome('a')
print longest_palindrome('')
A working Python solution.
def shuffle(string):
counter = {}
# one character count > n/2 then can't suffle
n = len(string)
for char in string:
if char in counter:
counter[char] += 1
if counter[char] > (n+1)/2:
return None
else:
counter[char] = 1
sorted_string = sorted(string)
shuffled_string = ""
previous_char = ""
queue = []
# AAABBCCDD
# result: ABCD
# queue: DCBAA
for char in string:
if char == previous_char:
queue.insert(0,char)
for queue_char in char:
if queue_char != previous_char:
shuffled_string += queue_char
previous_char = queue_char
else:
shuffled_string += char
previous_char = char
if len(queue) > 0:
for queue_char in queue:
previous_char = ""
for i,char in enumerate(shuffled_string):
if queue_char != previous_char and queue_char != char:
shuffled_string = shuffled_string[:i] + queue_char + shuffled_string[i:]
break
previous_char = char
return shuffled_string
print shuffle('ABCDAABCD')
print shuffle('aaaabbbca')
print shuffle('aaaabbbcaa')
print shuffle('')
print shuffle('a')
A working solution in Python using recursion.
- kojino November 27, 2016