String manipulation ought to be avoided II
First attempt to solving this problem led to time limit exceeded, too much string manipulation. One option to work around it is to make use of the String constructor that lets you create a string of length N composed of the same character. This problem is also a great example of frequency-counting strategy, common with string problems where the constraint is to use lower case characters only.
I also nowadays like to use OpenAI ChatGPT 4.5+ to help me analyze the time complexity of some of these algorithms. Fos this one, for example, the analysis is clear that the time complexity is linear. Code is down below, cheers, ACC.
Smallest Palindromic Rearrangement I - LeetCode
You are given a string s
.
Return the palindromic of s
.
Example 1:
Input: s = "z"
Output: "z"
Explanation:
A string of only one character is already the lexicographically smallest palindrome.
Example 2:
Input: s = "babab"
Output: "abbba"
Explanation:
Rearranging "babab"
→ "abbba"
gives the smallest lexicographic palindrome.
Example 3:
Input: s = "daccad"
Output: "acddca"
Explanation:
Rearranging "daccad"
→ "acddca"
gives the smallest lexicographic palindrome.
Constraints:
1 <= s.length <= 105
s
consists of lowercase English letters.s
is guaranteed to be palindromic.
public string SmallestPalindrome(string s) { int[] frequency = new int[26]; foreach (char c in s) frequency[(int)(c - 'a')]++; string left = ""; string right = ""; string mid = ""; for (int i = 0; i < frequency.Length; i++) { if (frequency[i] % 2 == 0) { int n = frequency[i] / 2; string temp = new string((char)(i + 'a'), n); left = left + temp; right = temp + right; } else { int n = (frequency[i] - 1) / 2; string temp = new string((char)(i + 'a'), n); left = left + temp; right = temp + right; mid = ((char)(i + 'a')).ToString(); } } return left + mid + right; }
Comments
Post a Comment