Python solution with explanation - easy to understand


  • 0
    S

    The trick in this problem is at every step, you want to see if you should do an extra copy step. If you maximize the copies then you will get the minimum answer. To check if you can do a copy you check if the leftover number of As is divisible by the current length. If it is, you can be sure that the rest of the string can be completed by doing a copy. You keep track of a count, current copied length and the currentLength - and the end of every step you add current copied length to currentLength and increase count by one.

        def minSteps(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n <= 1:
                return 0
            else:
                curLen = 1
                count = 0
                copied = 0
                while curLen < n:
                    if (n - curLen) % curLen == 0:
                        copied = curLen 
                        count += 1
                    curLen += copied  
                    count += 1 
            return count
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.