LeetCode Contest Solution

Problem 1:

2696. Minimum String Length After Removing Substrings

You are given a string s consisting only of uppercase English letters.

You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.

Example 1:

Input: s = "ABFCACDB"
Output: 2
Explanation: We can do the following operations:
- Remove the substring "ABFCACDB", so s = "FCACDB".
- Remove the substring "FCACDB", so s = "FCAB".
- Remove the substring "FCAB", so s = "FC".
So the resulting length of the string is 2.
It can be shown that it is the minimum length that we can obtain.

Example 2:

Input: s = "ACBBD"
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.

Constraints:

• 1 <= s.length <= 100

• s consists only of uppercase English letters.

Solution:

Based on the constraints we can just simulate the problem, but we'll do it optimally using stack.

Code:

class Solution:
    def minLength(self, s: str) -> int:
        stack = []
        for c in s:
            if stack and ((c == 'B' and stack[-1] == 'A') or (c == 'D' and stack[-1] == 'C')):
                stack.pop()
            else:
                stack.append(c)
        return len(stack)

Explanation:

Good problems based on Stack:

https://leetcode.com/list/r5ae65q1

---

Problem 2:

2697. Lexicographically Smallest Palindrome

You are given a string s consisting of lowercase English letters, and you are allowed to perform operations on it. In one operation, you can replace a character in s with another lowercase English letter.

Your task is to make s a palindrome with the minimum number of operations possible. If there are multiple palindromes that can be made using the minimum number of operations, make the lexicographically smallest one.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Return the resulting palindrome string.

Example 1:

Input: s = "egcfe"
Output: "efcfe"
Explanation: The minimum number of operations to make "egcfe" a palindrome is 1, and the lexicographically smallest palindrome string we can get by modifying one character is "efcfe", by changing 'g'.

Example 2:

Input: s = "abcd"
Output: "abba"
Explanation: The minimum number of operations to make "abcd" a palindrome is 2, and the lexicographically smallest palindrome string we can get by modifying two characters is "abba".

Example 3:

Input: s = "seven"
Output: "neven"
Explanation: The minimum number of operations to make "seven" a palindrome is 1, and the lexicographically smallest palindrome string we can get by modifying one character is "neven".

Constraints:

• 1 <= s.length <= 1000

• s consists of only lowercase English letters**.**

Solution :

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        #change it into list
        string = list(s)
        #two pointer
        n = len(s)
        for left in range(n//2):
            if string[left] != string[n-left-1]:
                #change it but it should be lexicographically smaller
                if string[left] < string[n-left-1]:
                    string[n-left-1] = string[left]
                else:
                    string[left] = string[n-left-1]

        return "".join(string)

Explanation:

In order to be a string palindrome, the reversal of string and string should be exact.

• i.e. abba is a palindrome because the reverse of abba is "abba", and 'abbd' is not a palindrome because it's reversal i.e. 'dbba' is not the same as the original string.

• In this particular problem, we go to the half-length of the string.

  • and compare 1st and last character, 2nd and the second last character if it is not the same then make it the same.

  • How-> As said in the problem lexicographically smallest.

---

Problem-3:

2698. Find the Punishment Number of an Integer

Given a positive integer n, return the punishment number of n.

The punishment number of n is defined as the sum of the squares of all integers i such that:

• 1 <= i <= n

• The decimal representation of i * i can be partitioned into contiguous substrings such that the sum of the integer values of these substrings equals i.

Example 1:

Input: n = 10
Output: 182
Explanation: There are exactly 3 integers i that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1.
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0.
Hence, the punishment number of 10 is 1 + 81 + 100 = 182

Example 2:

Input: n = 37
Output: 1478
Explanation: There are exactly 4 integers i that satisfy the conditions in the statement:
- 1 since 1 * 1 = 1. 
- 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1. 
- 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0. 
- 36 since 36 * 36 = 1296 and 1296 can be partitioned into 1 + 29 + 6.
Hence, the punishment number of 37 is 1 + 81 + 100 + 1296 = 1478

Constraints:

• 1 <= n <= 1000

Solution:

• 1 <= n <= 1000 gives us a hint that this problem can be solved using brute-force

class Solution:
    def punishmentNumber(self, n: int) -> int:

        def isPossible(num, idx,digitSum, currSum = 0):
            #base case
            if idx == len(num):
                return currSum == digitSum

            for nextIdx in range(idx, len(num)):
                if currSum > digitSum:
                    break       
                if isPossible(num, nextIdx+1, digitSum, currSum + int(num[idx : nextIdx+1])):
                    return True

            return False


        ans = 0
        for i in range(1, n + 1):
            if isPossible(str(i*i), 0, i):
                ans += i * i

        return ans

Explanation:

• loop through number till [1, n] as stated in the problem.

• we will use recursion to find out if it's possible to partition the number

$$i*i \ where\ 1

• Check if any partition exists such that-

$$sum(numberString[0...len(i*i)])== i$$

• Sum the answer with i*i each time such a partition exists.

If you are new to recursion follow this blog, I am working on recursion series.

Cheer!

Summary:

• Overall the contest was very good, problems 1 and 2 were easy 3 was medium-hardish, 4th one was hard enough, I just ignored it haha.😁

---

😁If you enjoyed this article, show your support by hitting the like💜 and comment💬buttons.

Subscribe to my newsletter to stay updated and never miss out on future content📩.