767. Reorganize String

'''
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return "" if not possible.
Example 1:
Input: s = "aab"
Output: "aba"
'''
#M1
class Solution:
    def reorganizeString(self, s: str) -> str:
        d=Counter(s)
        n=len(s)
        mkey,mval = d.most_common(1)[0]

        if mval > (n+1)>>1:
            return ""
        ans = [None]*n

        i = 0
        for _ in range(mval):
            ans[i] = mkey
            i = (i+2)%n

        for key in d.keys():
            if key == mkey:continue
            for _ in range(d[key]):
                while ans[i] != None:i += 1
                ans[i] = key
                i = (i+2)%n

        return ''.join(ans)
#M2
class Solution:
    def reorganizeString(self, s: str) -> str:
        n=len(s)
        freq=[0]*26
        for i in s:
            freq[ord(i)-97]+=1
        maxi = max(freq) #max frequency caluculate
        if maxi>(n+1)//2 : #if this condition happens then surely you cant make reorganized string
            return ""
        ans = [None]*n
        char = chr(freq.index(maxi)+97)

        idx=0
        while maxi:
            ans[idx]=char
            idx +=2
            maxi-=1
            if idx>=n:
                idx=1

        freq[ord(char)-97]=0

        for i in range(26):
            while freq[i]>0:
                freq[i]-=1
                ans[idx]= chr(i+97)
                idx+=2
                if idx>=n:
                    idx=1

        return ''.join(ans)