Leetcode 38: Count and Say

1. Problem Statement (Simple Explanation):

We define a sequence of strings countAndSay(n):

Base:

countAndSay(1) = "1"

Recursive:

countAndSay(n) = RLE(countAndSay(n-1))
where RLE = run-length encoding of the previous term.

Run-Length Encoding (RLE) here means:

Read the string left to right.
Group consecutive identical characters.
For each group k of character c, append:

the count k followed by the character c.

Example of RLE:

"3322251":

"33" → "23" (two 3s)
"222" → "32" (three 2s)
"5" → "15" (one 5)
"1" → "11" (one 1)

Combined: "23321511".

You must return countAndSay(n) as a string.

2. Examples:

Example 1:

Input: n = 4

Sequence:

n = 1: "1"
n = 2: RLE("1") → one 1 → "11"
n = 3: RLE("11") → two 1s → "21"
n = 4: RLE("21") → one 2, then one 1 → "12" + "11" = "1211"

Output: "1211"

Example 2:

Input: n = 1

Output: "1" (Base case.)

3. Approach – Iterative Generation (Recommended):

We generate the sequence iteratively from 1 up to n.

Idea:

Start with current = "1".
For step from 2 to n:

Set current = RLE(current).

RLE helper:

Given a string s, produce its run-length encoding:

Initialize an empty result builder.
Iterate over s with index i:

Set count = 1.
While i + 1 < len(s) and s[i+1] == s[i], increment count and i.
Append count (as string) and s[i] to result.

Return the result as a string.

Pseudo-code:

Complexity:

Let Lk = length(countAndSay(k)). Empirically, Lk stays manageable for n <= 30.

For each step:

We scan the current string once.

Total complexity:

Time: Approximately O(k=1nLk); for n <= 30, this is very safe.
Space: O(L*k) for the final string.

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code:

Comments

Leetcode 1: Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to return the indices of two numbers in the array such that: Conditions: Each input has exactly one solution . You cannot use the same element twice . You can return the answer in any order . 2. Examples Example 1 Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0]+nums[1]=2+7=9 So we return [0, 1]. Example 2 Input: ...

Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input: s = "pwwkew" Output: 3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a single digit . The digits are stored in reverse order (i.e., the 1’s digit is at the head). You need to add the two numbers and return the sum as a linked list , also in reverse order. You can assume: There are no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input: l1 = [2,4,3] l2 = [5,6,4] Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output: [7,0,8] Explanation: ...

codesprint with rishav

Search This Blog