Given a string s, replace each English letter with the next letter of the same case, wrapping from z to a and from Z to A. Return the transformed string with all other characters preserved.
Example 1
Input: s = "ayZ zY7!"
Output: "bzA aZ7!"
Explanation: The letters a, y, and Y advance to b, z, and Z. The letters Z and z wrap to A and a. The output preserves the space, digit, and exclamation mark at their original positions.
Example 2
Input: s = "9-?"
Output: "9-?"
Explanation: The string contains only a digit and punctuation, so the output matches the input.
Approach
Each output character depends only on the input character at the same position. Adding one to a letter's character code gives the next letter for a through y and A through Y. Wrapping requires an explicit replacement of z with a and Z with A. If a character is not a letter, keep it as it is.
A single scan is enough because a change at one position has no effect on any other position. Every position can affect the result, so any correct solution must inspect all n characters in the worst case.
Algorithm
Start with a copy of the input characters for the result.
Examine each character from left to right, including when the input has just one character.
For a lowercase letter, write
ain place ofzand advance every other lowercase letter by one character code.For an uppercase letter, write
Ain place ofZand advance every other uppercase letter by one character code.If the character is not a letter, keep it as it is.
Return the result after the last character has been examined.
Dry Run
Change Every Letter with the Next Lexicographic
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the string with each English letter shifted forward once. string shiftCharacters(const string& s) { string result = s; // Check the original character at each position before updating the copy. for (size_t i = 0; i < s.size(); i++) { char letter = s[i]; // Shift within the lowercase range and wrap its last letter. if (letter >= 'a' && letter <= 'z') { result[i] = (letter == 'z') ? 'a' : letter + 1; } // Shift within the uppercase range and wrap its last letter. else if (letter >= 'A' && letter <= 'Z') { result[i] = (letter == 'Z') ? 'A' : letter + 1; } } return result; }};// Driver codeint main() { // instance for class Solution Solution sol; string s = "ayZ zY7!"; cout << sol.shiftCharacters(s) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N). Copying the string, checking each character, and forming the returned string all take linear time.
Space Complexity: O(N). The implementations store a copy of the characters, which serves as the output in C++ and as a buffer for constructing the output in the other languages.
Interview follow-up Questions
The ranges select exactly the letters the problem shifts. A general alphabetic check can also recognize letters such as é, which this task preserves.
Be the first to add a comment.