Mastering Development in Python: Assignment 4 | Python- Mastering Development in Python - Software Development PDF Download

Q1: Given a 0-indexed string s, repeatedly perform the following operation any number of times:

Choose an index i in the string, and let c be the character in position i. Delete the closest occurrence of c to the left of i (if any) and the closest occurrence of c to the right of i (if any).

Your task is to minimize the length of s by performing the above operation any number of times.

Return an integer denoting the length of the minimized string.

Example 1:

Input: s = "aaabc"

Output: 3

Explanation: In this example, s is "aaabc". We can start by selecting the character 'a' at index 1. We then remove the closest 'a' to the left of index 1, which is at index 0, and the closest 'a' to the right of index 1, which is at index 2. After this operation, the string becomes "abc". Any further operation we perform on the string will leave it unchanged. Therefore, the length of the minimized string is 3.

Example 2:

Input: s = "cbbd"

Output: 3

Explanation: For this we can start with character 'b' at index 1. There is no occurrence of 'b' to the left of index 1, but there is one to the right at index 2, so we delete the 'b' at index 2. The string becomes "cbd" and further operations will leave it unchanged. Hence, the minimized length is 3. 

Example 3:

Input: s = "dddaaa"

Output: 2

Explanation: For this, we can start with the character 'd' at index 1. The closest occurrence of a 'd' to its left is at index 0, and the closest occurrence of a 'd' to its right is at index 2. We delete both index 0 and 2, so the string becomes "daaa". In the new string, we can select the character 'a' at index 2. The closest occurrence of an 'a' to its left is at index 1, and the closest occurrence of an 'a' to its right is at index 3. We delete both of them, and the string becomes "da". We cannot minimize this further, so the minimized length is 2.

 Constraints:

1 <= s.length <= 100

s contains only lowercase English letters

Ans: 

Q2: 

There is a robot starting at the position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

You are given a string moves that represents the move sequence of the robot where moves[i] represents its ith move. Valid moves are 'R' (right), 'L' (left), 'U' (up), and 'D' (down).

Return true if the robot returns to the origin after it finishes all of its moves, or false otherwise.

Note: The way that the robot is "facing" is irrelevant. 'R' will always make the robot move to the right once, 'L' will always make it move left, etc. Also, assume that the magnitude of the robot's movement is the same for each move.

Example 1:

Input: moves = "UD"

Output: true

Explanation: The robot moves up once, and then down once. All moves have the same magnitude, so it ended up at the origin where it started. Therefore, we return true.

Example 2:

Input: moves = "LL"

Output: false

Explanation: The robot moves left twice. It ends up two "moves" to the left of the origin. We return false because it is not at the origin at the end of its moves.

 Constraints:

1 <= moves.length <= 2 * 104

moves only contains the characters 'U', 'D', 'L' and 'R'.

Ans: 

Q3: You are given a string s. Reorder the string using the following algorithm:

Pick the smallest character from s and append it to the result.

Pick the smallest character from s which is greater than the last appended character to the result and append it.

Repeat step 2 until you cannot pick more characters.

Pick the largest character from s and append it to the result.

Pick the largest character from s which is smaller than the last appended character to the result and append it.

Repeat step 5 until you cannot pick more characters.

Repeat the steps from 1 to 6 until you pick all characters from s.

In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return the result string after sorting s with this algorithm.

Example 1:

Input: s = "aaaabbbbcccc"

Output: "abccbaabccba"

Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"

After steps 4, 5 and 6 of the first iteration, result = "abccba"

First iteration is done. Now s = "aabbcc" and we go back to step 1

After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"

After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"

Example 2:

Input: s = "rat"

Output: "art"

Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

 Constraints:

1 <= s.length <= 500

s consists of only lowercase English letters.

Ans: 

Q4:  You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"

Output: 1

Explanation: s is already a palindrome, so its entirety can be removed in a single step.

Example 2:

Input: s = "abb"

Output: 2

Explanation: "abb" -> "bb" -> "". 

Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"

Output: 2

Explanation: "baabb" -> "b" -> "". 

Remove palindromic subsequence "baab" then "b".

 Constraints:

1 <= s.length <= 1000

s[i] is either 'a' or 'b'.

Ans: 

Q5: 

Given a string s, return true if s is a good string, or false otherwise.

A string s is good if all the characters that appear in s have the same number of occurrences (i.e., the same frequency).

Example 1:

Input: s = "abacbc"

Output: true

Explanation: The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.

Example 2:

Input: s = "aaabb"

Output: false

Explanation: The characters that appear in s are 'a' and 'b'.

'a' occurs 3 times while 'b' occurs 2 times, which is not the same number of times.

 Constraints:

1 <= s.length <= 1000

s consists of lowercase English letters.

Ans: