TCS Digital Coding Questions 2024 | Problem Statement And Solutions

In This Post We Are Solving TCS Digital Coding Questions 2024 Problem Statement And Its Solutions Which May Help You To Practice Your Coding.

Sure! Let’s clearly define the problem, provide a detailed solution in Python, and include a thorough explanation.

Problem Definition – TCS Digital Coding Questions 2024

Problem: Breaking a Palindrome

A palindrome reads the same forwards and backwards (e.g., “mom”, “racecar”). Given a string palindromeStr that is a palindrome, you need to modify exactly one character to create a new string that meets the following conditions:

1. The new string is lexicographically smaller than the original palindrome.
2. The new string is the smallest possible string that can be created by making exactly one change.
3. The new string is not a palindrome.

If it’s impossible to create such a string, return “IMPOSSIBLE”.

Function Signature:

def breakPalindrome(palindromeStr: str) -> str:

Input:

• palindromeStr (string): The original palindrome string.

Output:

• (string): The resulting string, or “IMPOSSIBLE” if it cannot be formed.

Example

Example 1:

palindromeStr = "aaabbaaa"

Output:

"aaaabaaa"

Explanation:
Possible strings lower alphabetically than “aaabbaaa” after one change are [“aaaabaaa”, “aaabaaaa”]. “aaaabaaa” is the lowest string that is not a palindrome.

Example 2:

palindromeStr = "bab"

Output:

"aab"

Explanation:
Possible strings lower alphabetically than “bab” after one change are [“aab”, “baa”]. “aab” is the lowest string that is not a palindrome.

Example 3:

palindromeStr = "aaa"

Output:

"IMPOSSIBLE"

Explanation:
There are no strings lower alphabetically than “aaa” after one change that are not palindromes. Thus, it is impossible.

Solution

Here is the Python solution to solve the problem:

def breakPalindrome(palindromeStr):
    n = len(palindromeStr)

    # Edge case: If the string length is 1, it's impossible to make it non-palindromic
    if n == 1:
        return "IMPOSSIBLE"

    # Try to change the first non-'a' character to 'a'
    for i in range(n // 2):
        if palindromeStr[i] != 'a':
            new_str = palindromeStr[:i] + 'a' + palindromeStr[i + 1:]
            return new_str

    # If no change was made in the loop, it means all characters in the first half are 'a'
    # Change the last character to 'b'
    new_str = palindromeStr[:-1] + 'b'
    return new_str

# Testing the function with provided examples
print(breakPalindrome("bab"))  # Output: "aab"
print(breakPalindrome("aaa"))  # Output: "IMPOSSIBLE"
print(breakPalindrome("acca")) # Output: "aaca"

Explanation

Edge Case Handling:

• If the length of palindromeStr is 1, return “IMPOSSIBLE” because it’s not possible to make a single character string non-palindromic by changing one character.

Modification of the First Non-‘a’ Character: TCS Digital Coding Questions 2024

• Iterate through the first half of the string. If any character is not ‘a’, change it to ‘a’. This ensures the result is the lexicographically smallest non-palindromic string.
• We only need to ensure it’s not a palindrome, so we check only the first half to avoid duplicating changes across the symmetrical part of the palindrome.

Handling All ‘a’ Strings: TCS Digital Coding Questions 2024

• If the string is all ‘a’s (and thus no change was made in the loop), change the last character to ‘b’. This ensures it’s still the smallest possible change to make it non-palindromic.

Additional Test Cases

Here are additional test cases to further validate the solution:

# Additional test cases
print(breakPalindrome("abccba"))  # Expected: "aaccba"
print(breakPalindrome("aaaaa"))   # Expected: "aaaab"
print(breakPalindrome("a"))       # Expected: "IMPOSSIBLE"
print(breakPalindrome("abcba"))   # Expected: "aacba"
print(breakPalindrome("aaaabaaa")) # Expected: "aaabaaaa"

This solution handles various edge cases including all ‘a’ strings, single character strings, and general palindromic strings effectively.

Problem Statement 2 – TCS Digital Coding Questions 2024

To solve the problem of balancing parentheses in a string by inserting the minimum number of characters, we need to understand the criteria for a balanced string of parentheses:

1. The number of opening parentheses ‘(‘ must equal the number of closing parentheses ‘)’.
2. At any point in the string, the number of closing parentheses ‘)’ should not exceed the number of opening parentheses ‘(‘ that precede them.

To achieve this, we can use a simple counting mechanism to track unmatched parentheses as we iterate through the string:

• left_balance: Tracks the number of unmatched ‘(‘.
• right_balance: Tracks the number of unmatched ‘)’.

Steps to solve the problem: TCS Digital Coding Questions 2024

1. Initialize two counters left_balance and right_balance to zero.
2. Traverse through each character in the string:

• If the character is ‘(‘, increment left_balance (indicating an unmatched opening parenthesis).
• If the character is ‘)’:
  • If left_balance is greater than zero, decrement left_balance (indicating that this ‘)’ matches with a previous unmatched ‘(‘).
  • If left_balance is zero, increment right_balance (indicating an unmatched closing parenthesis).

The total number of insertions needed to balance the string will be the sum of left_balance and right_balance.

Example Walkthrough: TCS Digital Coding Questions 2024

Let’s take an example to understand this:

Example 1: TCS Digital Coding Questions 2024

• Input: s = '()))'
• Iteration:
• (: left_balance = 1, right_balance = 0
• ): left_balance = 0, right_balance = 0 (matches with previous ()
• ): left_balance = 0, right_balance = 1 (no matching ()
• ): left_balance = 0, right_balance = 2 (no matching ()
• Result: left_balance + right_balance = 0 + 2 = 2

Example 2:

• Input: s = '(()))'
• Iteration:
• (: left_balance = 1, right_balance = 0
• (: left_balance = 2, right_balance = 0
• ): left_balance = 1, right_balance = 0 (matches with previous ()
• ): left_balance = 0, right_balance = 0 (matches with previous ()
• ): left_balance = 0, right_balance = 1 (no matching ()
• Result: left_balance + right_balance = 0 + 1 = 1

Implementation in Python: TCS Digital Coding Questions 2024

def getMin(s):
    left_balance = 0
    right_balance = 0

    for char in s:
        if char == '(':
            left_balance += 1
        elif char == ')':
            if left_balance > 0:
                left_balance -= 1
            else:
                right_balance += 1

    return left_balance + right_balance

# Sample Test Cases
print(getMin('()))'))  # Output: 2
print(getMin('()()'))  # Output: 0
print(getMin('(()))')) # Output: 1
print(getMin('))(('))  # Output: 4

Explanation of the Function: TCS Digital Coding Questions 2024

• The function getMin takes a string s as input.
• left_balance is used to count unmatched ‘(‘.
• right_balance is used to count unmatched ‘)’.
• For each character in the string:
• If it’s ‘(‘, increment left_balance.
• If it’s ‘)’:
  • If there’s an unmatched ‘(‘, decrement left_balance (matching the current ‘)’ with a previous ‘(‘).
  • Otherwise, increment right_balance (indicating an unmatched ‘)’).
• Finally, return the sum of left_balance and right_balance as the minimum number of insertions required to balance the string.

Home

Latest Posts