Sponsored
Sponsored
In this approach, we calculate the cumulative shift for each character and apply it directly. We start from the first character and compute the required shift by summing all applicable shift values for each character position. After calculating the cumulative shift, we adjust each character in the string accordingly.
Time Complexity: O(n^2) where n is the length of the string due to the nested loops.
Space Complexity: O(1) since no extra space other than for variables is used.
1public class ShiftingLetters {
2 public static String shiftingLetters(String s, int[] shifts) {
3 char[] chars = s.toCharArray();
4 for (int i = 0; i < chars.length; i++) {
5 int totalShift = 0;
6 for (int j = 0; j <= i; j++) {
7 totalShift += shifts[j];
8 }
9 totalShift %= 26;
10 chars[i] = (char)((chars[i] - 'a' + totalShift) % 26 + 'a');
11 }
12 return new String(chars);
13 }
14
15 public static void main(String[] args) {
16 String s = "abc";
17 int[] shifts = {3, 5, 9};
18 System.out.println(shiftingLetters(s, shifts));
19 }
20}This Java solution employs cumulative additions over shifts array and updates the character array using ASCII offset.
This approach optimizes the shift of letters by computing the cumulative shift from the last character to the first. It reduces the overhead of multiple summations using a single pass through the shifts array from back to front.
Time Complexity: O(n), processing each character once.
Space Complexity: O(1).
1#include <iostream>
#include <vector>
using namespace std;
string shiftingLettersOptimized(string s, vector<int>& shifts) {
int cumulative_shift = 0;
for (int i = s.length() - 1; i >= 0; i--) {
cumulative_shift = (cumulative_shift + shifts[i]) % 26;
s[i] = (s[i] - 'a' + cumulative_shift) % 26 + 'a';
}
return s;
}
int main() {
string s = "abc";
vector<int> shifts = {3, 5, 9};
cout << shiftingLettersOptimized(s, shifts) << endl;
return 0;
}C++ leverages backward computation through the shifts array, achieving efficiency by avoiding redundant calculations.