Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1328.html

1328. Break a Palindrome (Medium)

Given a palindromic string palindrome, replace exactly one character by any lowercase English letter so that the string becomes the lexicographically smallest possible string that isn't a palindrome.

After doing so, return the final string.  If there is no way to do so, return the empty string.

 

Example 1:

Input: palindrome = "abccba"
Output: "aaccba"

Example 2:

Input: palindrome = "a"
Output: ""

 

Constraints:

• 1 <= palindrome.length <= 1000
• palindrome consists of only lowercase English letters.

Related Topics:
String

Solution 1.

• Java
• C++

• class Solution {
      public String breakPalindrome(String palindrome) {
          char[] array = palindrome.toCharArray();
          int length = array.length;
          if (length == 1)
              return "";
          int halfMax = length / 2;
          for (int i = 0; i < halfMax; i++) {
              char c = array[i];
              if (c != 'a') {
                  array[i] = 'a';
                  return new String(array);
              }
          }
          array[length - 1] = 'b';
          return new String(array);
      }
  }
  

• // OJ: https://leetcode.com/problems/break-a-palindrome/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      string breakPalindrome(string s) {
          int N = s.size();
          if (N == 1) return "";
          for (int i = 0, end = N / 2; i < end; ++i) {
              if (s[i] != 'a') {
                  s[i] = 'a';
                  return s;
              }
          }
          s[N - 1] = 'b';
          return s;
      }
  };
  

All Problems

All Solutions