Daily Leetcode Challenge | DEC 17 | Construct String With Repeat Limit

[@darshankumar5546]

#approach -2 (better than optimal leetcode solution):
# tc=O(n+26+26*log(26))=O(n)
# sc=O(26+26)=O(const)
import heapq
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
freq=[0 for i in range(26)]
asciiOf_a=ord('a')
for i in s:
index=ord(i)-ord('a')
freq[index]+=1
maxHeap=[]
for i in range(26):
if(freq[i]!=0):
maxHeap.append([-i,freq[i]])
heapq.heapify(maxHeap)
#print(freq)
ans=''
#print(maxHeap)
while(maxHeap):
index,frequency=heapq.heappop(maxHeap)
index*=-1
character=chr(index+asciiOf_a)
while(frequency!=0):
if(ans and ans[-1]==character):
#insert next largest character
if(len(maxHeap)==0):
return ans
nextLargestCharacter=chr(maxHeap[0][0]*(-1)+asciiOf_a)
maxHeap[0][1]-=1
if(maxHeap[0][1]==0):
heapq.heappop(maxHeap)
ans+=nextLargestCharacter
#insert 'character' repeatLimit or lower, times
NoOfcharsToBeWritten=min(repeatLimit,frequency)
frequency-=NoOfcharsToBeWritten
ans+=character*NoOfcharsToBeWritten
return ans

[@darshankumar5546]

Hindi Explanation: ua-cam.com/video/Dpaz84zT4V4/v-deo.html

[@darshankumar5546]

#approach -1
# tc=O(n+26*n)=O(n)
# sc=O(26)=O(const)
class Solution:
def repeatLimitedString(self, s: str, repeatLimit: int) -> str:
freq=[0 for i in range(26)]
asciiOf_a=ord('a')
for i in s:
index=ord(i)-ord('a')
freq[index]+=1
#print(freq)
ans=''
def nextLargestChar(index):
nonlocal freq
for i in range(index-1,-1,-1):
if(freq[i]!=0):
freq[i]-=1
return chr(i+asciiOf_a)
return '-1'

for i in range(25,-1,-1):
if(freq[i]==0):
continue
character=chr(i+asciiOf_a)
while(freq[i]!=0):
if(ans and ans[-1]==character):
#insert next largest character
nextLargestCharacter=nextLargestChar(i)
if(nextLargestCharacter=='-1'):
return ans
ans+=nextLargestCharacter
#insert 'character' repeatLimit or lower, times
frequency=min(repeatLimit,freq[i])
freq[i]-=frequency
ans+=character*frequency

return ans
# ab vs ac => ac > ab
# ab vs abc => abc > ab