0038. Count and Say

Medium | String | 36 ms (96.09%), 14.3 MB (74.99%)

❓ Problem Statement

Source: LeetCode - Count and Say GitHub: Solution / Performance

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = "1"

• countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you "say" a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

Refer to examples for a more clear explanation.

✍🏻 Constraints & Example

Constraints:

• 1 <= n <= 30

# n = 1
1      #

# n = 2
11     # one 1's

# n = 3
21     # two 1's

# n = 4
1211   # one 2, and one 1.

# n = 5
111221 # one 1, one 2, and two 1's.

💡 Ideas

Referring to each char in the previous sequence and record the previous char to check whether we need to do accumulation or restart the counter with the new previous char.

s = '1'      # base case
s = '11'     # preChar = 1, do accumulation because s[i] == s[i+1]
s = '21'     # preChar = 2, restart counter because s[i] != s[i+1]

s = '1211'   # preChar = 1, counter = 1  ->  f'{counter}{preChar}'
             # preChar = 2, counter = 1
             # preChar = 1, counter = 2
             
s = '111221' # preChar = 1, counter = 3  ->  f'{counter}{preChar}' 
             # preChar = 2, counter = 2
             # preChar = 1, counter = 1

🤖 Python3

class Solution:
    def countAndSay(self, n: int) -> str:
        # (base case)
        if n == 1: return '1'
        
        # ==================================================
        #  String + Math                                   =
        # ==================================================
        # time  : O(nk)
        # space : O(1)
        
        ret = '1'
        
        for _ in range(n - 1):
            prev, counter = ret[0], 0
            tmp = ''
            
            for c in ret:
                if prev != c:
                    tmp += str(counter) + prev
                    prev, counter = c, 1
                else:
                    counter += 1
                    
            tmp += str(counter) + prev
            ret = tmp
            
        return ret

🤖 Java

class Solution {
    /**  
     * @time  : O(nk)
     * @space : O(1)
     */

    public String countAndSay(int n) {
        String ret = "1";
        
        /* base case */
        if(n == 1) return ret;
        
        for(int i=0 ; i<n-1 ; i++) {
            StringBuilder tmp = new StringBuilder();
            char prev = ret.charAt(0);
            int counter = 0;
            
            for(int j=0 ; j<ret.length() ; j++) {
                if(prev != ret.charAt(j)) {
                    tmp.append(counter);
                    tmp.append(prev);
                    prev = ret.charAt(j);
                    counter = 1;
                } else {
                    counter++;
                }
            }
            
            tmp.append(counter);
            tmp.append(prev);
            ret = tmp.toString();
        }
        
        return ret;
    }
}