[백준] 1213번: 팰린드롬 만들기

https://www.acmicpc.net/problem/1213

initial

I didnt get the part where if the given string is already a palindrome, in what logic do i return another palindrome?

turns out you return a palindrome with the ascending order of alphabets so not ZAAZ but AZZA. To do this, we sort the items - key (alphabets) and values (frequence) via sorted(dic.items()), where dic is Counter(given_string). Wait but i thought sorting doesnt work well with string. Oh it works well but i remember there was a doubt on this. But anyway, sorting alphabets works on ascii values so ‘a’ comes first when you sort dic.items().

my_dict = {'b': 2, 'a': 69, 'c': 3}
sorted_dict_items = sorted(my_dict.items())

print(sorted_dict_items)

[('a', 69), ('b', 2), ('c', 3)]

Btw it is not a palindrome when there is 2 or more alphabets that have odd frequence. Palindrome an have 0 or 1 alphabet (ABBA, ABBBAA) with odd frequency but no more than 1. So we do that logic via a count int variable.

but why is my code wrong?

from collections import Counter

def make_palindrome(s):
    char_count = Counter(s)
    
    odd_count_chars = [char for char, count in char_count.items() if count % 2 != 0]
    # Check for palindrome possibility
    if len(odd_count_chars) > 2:
        return "I'm Sorry Hansoo"

    # Construct half of the palindrome
    half_palindrome = []
    for char, count in list(sorted(char_count.items())):
        half_palindrome.extend([char] * (count // 2))
    
    # Add one instance of characters with odd frequencies
    if odd_count_chars:
        half_palindrome.append(odd_count_chars[0])
        the_other = list(reversed(half_palindrome))[1:]
        full_palindrome = half_palindrome + the_other
    else:
        full_palindrome = half_palindrome + half_palindrome[::-1]

    return "".join(full_palindrome)

# Example usage
input_string = input()
result = make_palindrome(input_string)
print(result)

solution

much more concise than mine but why is mine wrong fk

he used string. a clever trick is he assigned a mid variable of "" so that when there is no alphabet with odd frequency to be added at the middle, the overall logic wont be affected

from collections import Counter

hola = input()
dic = Counter(hola)
tmp = ''

count = 0
mid = ''

for key, val in sorted(dic.items()):
    if val % 2 == 1:
        count += 1
        mid = key
        if count == 2:
            print("I'm Sorry Hansoo")
            exit()

    tmp += key * (val // 2)

print(tmp + mid + tmp[::-1])

revisited may 11th 2024

always the most impt thing is finding out pattern.

I didnt know you could sort the Counter's items, which sorts the keys on ascending order. Anyway the pattern is you can only have up to one key with odd value (frequency of that character). If there are 2 keys with odd value, no matter the length of the string, it is invalid. So implement that.

revisited june 3rd 2024

yep we cant have 2 or more keys with odd frequencies. And i got it that we needed to sort dictionary's keys, though I couldnt think of using Counter. My bad. Use counter cuz it makes life easier

revisited june 27th 24

yep got it

complexity

The time complexity of your code is O(N log N) due to the sorting operation, where N is the length of the input string hola. The space complexity is O(N) because of the additional space used to store the dic, tmp, mid, and other variables, which grows linearly with the input size.

Here's the breakdown:

1. Counter Operation (dic): O(N)

   • The Counter operation takes O(N) time to count the occurrences of each character in the input string.

2. Sorting Operation (sorted(dic.items())): O(N log N)

   • Sorting the dictionary items takes O(N log N) time due to the built-in sorting algorithm.

3. Iterating Through Sorted Items and Constructing Palindrome (for loop): O(N)

   • The for loop iterates through the sorted items once, and the operations inside the loop take constant time for each item.

4. Space Complexity:

   • dic: O(N) - Storage for the dictionary.
   • tmp: O(N) - Storage for the temporary string.
   • mid: O(1) - Storage for the middle character.
   • Other variables: O(1) - Constant space for counters and loop variables.

Overall, the dominant factor in both time and space complexity is the sorting operation, making the overall complexity O(N log N) and O(N), respectively.