Change Every Letter with the Next Lexicographic

37
0

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 a in place of z and advance every other lowercase letter by one character code.

  • For an uppercase letter, write A in place of Z and 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

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 code
int 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.

ArraysTCS NQT

Read Similar Blogs

Comments0