Sequential Character Indexing

Easy

0/40

0 upvote

Problem statement

You are given a string S. Your task is to process this string and generate a new string (or sequence of numbers) based on the sequential count of each character's appearance.

The process is as follows:

1) Iterate through the input string from left to right. 2) For each character, determine how many times that specific character has appeared so far in the string. 3) If a character c is encountered for the 1st time, its count is 1. If it's encountered for the 2nd time, its count is 2, and so on. 4) Replace each character in the original string with its sequential count.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a single string S.

Output Format:

Print a single line containing the space-separated sequence of sequential counts corresponding to each character in the original string.

Note:

The counting is case-sensitive ('a' and 'A' are treated as different characters).

Spaces and other symbols should be counted just like letters.

Sample Input 1:

aba

Sample Output 1:

1 1 2

Explanation for Sample 1:

1.  The first character is 'a'. It's the 1st time we've seen 'a'. Output: 1.
2.  The second character is 'b'. It's the 1st time we've seen 'b'. Output: 1.
3.  The third character is 'a'. It's the 2nd time we've seen 'a'. Output: 2.
The final sequence is `1 1 2`.

Sample Input 2:

Hello World

Sample Output 2:

1 1 1 2 1 1 2 1 3 1

Explanation for Sample 2:

- 'H': 1st time -> 1
- 'e': 1st time -> 1
- 'l': 1st time -> 1
- 'l': 2nd time -> 2
- 'o': 1st time -> 1
- ' ': 1st time -> 1
- 'W': 1st time -> 1
- 'o': 2nd time -> 2
- 'r': 1st time -> 1
- 'l': 3rd time -> 3
- 'd': 1st time -> 1

Expected Time Complexity:

The expected time complexity is O(N), where N is the length of the string.

Constraints:

0 <= length of S <= 10^5
The string consists of standard ASCII characters.

Time limit: 1 sec

Approaches (1)

Approach 1

Sequential Character Indexing

Time Complexity

Time complexity is O(N), where N is the length of the string.

Space Complexity

(100% EXP penalty)

Sequential Character Indexing

Console