Task 1: Decode String
You are given an encoded string. Write a script to return the decoded string of the given encoded string. The encoding rule is: K[encoded_string], where the encoded_string inside the square brackets is repeated exactly K > 0 times.
Example Output
Input: $str = "2[3[a]]"
Output: "aaaaaa"
Input: $str = "2[a2[b]c]"
Output: "abbcabbc"
Logic
Use two stacks (or a stack of tuples) to handle nested repetitions. While parsing characters:
accumulate digit characters to form repeat count K; upon encountering '[', push the current repeat count and the previously accumulated string onto stacks and reset current values; upon ']', pop the multiplier and preceding string, then update the current string to prev_string + current_string * count.
Perl Solution
ch-1.pl
sub decode_string ($str) {
my @count_stack;
my @str_stack;
my $curr_str = '';
my $curr_num = 0;
for my $char ( split //, $str ) {
if ( $char =~ /\d/ ) {
$curr_num = $curr_num * 10 + $char;
}
elsif ( $char eq '[' ) {
push @count_stack, $curr_num;
push @str_stack, $curr_str;
$curr_num = 0;
$curr_str = '';
}
elsif ( $char eq ']' ) {
my $count = pop @count_stack;
my $prev_str = pop @str_stack;
$curr_str = $prev_str . ( $curr_str x $count );
}
else {
$curr_str .= $char;
}
}
return $curr_str;
}
Python Solution
ch-1.py
def decode_string(s: str) -> str:
"""Decode string formatted with K[encoded_string] repetitions."""
count_stack: list[int] = []
str_stack: list[str] = []
curr_str = ""
curr_num = 0
for char in s:
if char.isdigit():
curr_num = curr_num * 10 + int(char)
elif char == "[":
count_stack.append(curr_num)
str_stack.append(curr_str)
curr_num = 0
curr_str = ""
elif char == "]":
count = count_stack.pop()
prev_str = str_stack.pop()
curr_str = prev_str + curr_str * count
else:
curr_str += char
return curr_str
Task 2: Smallest String
You are given a string $s and an integer $k > 0. Choose one of the first $k letters and append it to the end of the string. Repeat this until you obtain the lexicographically smallest string.
Example Output
Input: $str = "dbca", $k = 1
Output: "adbc"
Input: $str = "geeks", $k = 2
Output: "eegks"
Logic
If k == 1, only cyclic rotations of the string are possible. We generate all cyclic shifts and pick the lexicographically smallest. If k >= 2, we can swap adjacent elements at will (equivalent to Bubble Sort moves), allowing any permutation to be formed; thus the result is simply all characters sorted alphabetically.
Perl Solution
ch-2.pl
sub smallest_string ( $s, $k ) {
my $len = length($s);
return $s if $len <= 1;
if ( $k > 1 ) {
return join( '', sort split //, $s );
}
my $smallest = $s;
my $curr = $s;
for ( 1 .. $len - 1 ) {
$curr = substr( $curr, 1 ) . substr( $curr, 0, 1 );
$smallest = $curr if $curr lt $smallest;
}
return $smallest;
}
Python Solution
ch-2.py
def smallest_string(s: str, k: int) -> str:
"""Return the lexicographically smallest string reachable."""
if len(s) <= 1:
return s
if k > 1:
return "".join(sorted(s))
smallest = s
curr = s
for _ in range(len(s) - 1):
curr = curr[1:] + curr[0]
if curr < smallest:
smallest = curr
return smallest