Practice Projects

Shifting Letters II

Problem Statement

Tumhe ek string s di gayi hai jo lowercase English letters se bani hui hai aur ek 2D integer array shifts diya gaya hai jaha shifts[i] = [starti, endi, directioni]. Har i ke liye, s ke characters ko starti se leke endi (inclusive) tak shift karo agar directioni = 1 hai to forward, aur agar directioni = 0 hai to backward shift karo.

Forward Shift:

  • Forward shift ka matlab hai agle letter se replace karna (so that ‘z’ becomes ‘a’).

Backward Shift:

  • Backward shift ka matlab hai pichle letter se replace karna (so that ‘a’ becomes ‘z’).

Final String:

  • Sab shifts apply karne ke baad jo final string milegi use return kare.

Example 1:

Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]

Output: "ace"

Explanation:

  1. Pehla shift: character ko index 0 se leke 1 tak backward shift karna.

    • s = "zac" ho jata hai.

  2. Doosra shift: character ko index 1 se leke 2 tak forward shift karna.

    • s = "zbd" ho jata hai.

  3. Teesra shift: character ko index 0 se leke 2 tak forward shift karna.

    • s = "ace" ho jata hai.

Example 2:

Input: s = "dztz", shifts = [[0,0,0],[1,1,1]]

Output: "catz"

Explanation:

  1. Pehla shift: character ko index 0 se leke 0 tak backward shift karna.

    • s = "cztz" ho jata hai.

  2. Doosra shift: character ko index 1 se leke 1 tak forward shift karna.

    • s = "catz" ho jata hai.

Constraints:

  • 1 <= s.length, shifts.length <= 5 * 10^4

  • shifts[i].length == 3

  • 0 <= start_i <= end_i < s.length

  • 0 <= direction_i <= 1

  • s sirf lowercase English letters ka hona chahiye.

Practice Projects

Shifting Letters II

Multiple Shifts
Problem:
Kai baar character shifts karne hain ek string me specific ranges ke andar.
Ek simple approach slow hoga kyunki hum baar-baar overlapping ranges ko process karenge.
Advanced Approach:
Hum use karte hain ek difference array jise hum sab shifts ko combine karke efficiently process kar saktein.
Yeh technique hume madad karti hai multiple shifts ko efficiently handle karne mein, sirf net effect pe dhyan dena hota hai har position par.
Kaise kaam karti hai yeh approach?
Example:
Maan lo humare paas ek string hai s = "abcde" aur shifts hai [[1, 3, 1], [2, 4, 0]].
Naive Approach: Har shift ke liye, hum corresponding range ko shift karenge.
Pehli shift (1-3 range forward shift):
a(bcd)e -> a(cde)e
String: a(cde)e
Doosri shift (2-4 range backward shift):
a(cde)e -> a(bcd)b
String: a(bcd)b
Yeh approach slow ho sakti hai agar kai overlapping shifts hain.
Difference Array Approach: Pehle, hum create karenge ek difference array.
First shift (1-3 forward): diff[1] += 1, diff[4] -= 1
Diff array: [0, 1, 0, 0, -1, 0]
Second shift (2-4 backward): diff[2] -= 1, diff[5] += 1
Diff array: [0, 1, -1, 0, -1, 1]
Calculate Net Effect:
Hum cumulative sum lenge difference array ka, taaki humara net shift calculate ho jaye har position pe.
Cum Sum: [0, 1, 0, 0, -1]
Index 1: +1 (forward shift)
Index 2: 0 (no shift)
Index 3: 0 (no shift)
Index 4: -1 (backward shift)
Index 5: 0 (no shift)
Apply Net Shifts:
Final string: adcbd

Intuition

Difference Array Approach:
Difference Array:
Ek difference array diff use karte hain taaki shifts ka effect ranges par record ho sake.
Har shift operation ke liye yeh steps follow karte hain:
+1 add karte hain (ya -1 for backward shifts) starting index se.
Subtract -1 (ya +1 for backward shifts) ending index ke baad tak, taaki waha effect end ho jaye.
Prefix Sum:
Cumulative sum compute karte hain difference array ka, taaki net shift determine kar sakein har position mein string ke andar.
Prefix sum range updates ko individual character shifts mein convert kar deta hai.
Modulo Operation:
Modulo 26 use karte hain taaki shifts wrap around alphabet mein ho (jaise z ko forward shift karne pe a banta hai).
Negative shifts normalize karne ke liye, 26 add karte hain taaki invalid indices na aaye.
Apply Shifts to the String:
String ke har character ke liye, new character calculate karte hain shift add kar ke (from prefix sum) uski position in the alphabet.Purane character ko replace karte hain nayi se.

Approach
Time Complexity: š¯‘‚(n + m)

  • š¯‘‚(m) to process all shifts:

    • Sab shifts ko process karna aur difference array ko update karna š¯‘‚(m) time leta hai.

    • Matlab, jitne shifts operation hain, utna time lagta hai.

  • š¯‘‚(n) to compute the prefix sum:

    • Cumulative sum (prefix sum) calculate karne aur string ko update karne me š¯‘‚(n) time lagta hai.

    • Matlab, jitni string ki length hai, utna time lagta hai.

Space Complexity: š¯‘‚(n)

  • š¯‘‚(n) difference array:

    • Difference array store karne ke liye š¯‘‚(n) space lagti hai.

    • Matlab, jitna string ka length hai, utna space lagta hai.

Solution

				
					class Solution {
  shiftingLetters(s, shifts) {
    const n = s.length; // String ki length n hai
    const prefixSum = new Array(n + 1).fill(0); // Prefix sum array, initially zero se filled

    // Har shift operation ko process karte hain
    for (const [start, end, direction] of shifts) {
      const value = direction === 1 ? 1 : -1; // Forward agar direction 1 hai to +1, aur 0 hai to -1
      prefixSum[start] += value; // Starting index par value add karte hain
      prefixSum[end + 1] -= value; // Ending index ke baad value subtract karte hain taaki effect end ho jaye
    }

    // Cumulative sum (prefix sum) calculate karte hain
    for (let i = 1; i < n; i++) {
      prefixSum[i] += prefixSum[i - 1];
    }

    let result = s.split(''); // String ko array of characters me convert karte hain
    for (let i = 0; i < n; i++) {
      let totalShifts = prefixSum[i]; // Total shifts her character ke liye nikalte hain

      totalShifts = ((totalShifts % 26) + 26) % 26; // Modulo 26 use karke shifts ko wrap around karte hain

      const charCode = s.char

  • String Length Calculate:

    • Sabse pehle, original string s ki length n calculate karte hain.

  • Prefix Sum Array Create:

    • Ek prefix sum array banate hain jo initially zero se filled hota hai. Yeh array har shift operation ka effect store karta hai.

  • Process Shifts:

    • Har shift operation ko process karte hain:

      • start, end aur direction values ko fetch karte hain.

      • value ko set karte hain: 1 for forward shift, aur -1 for backward shift.

      • prefixSum[start] par value add karte hain aur prefixSum[end + 1] par value subtract karte hain.

  • Calculate Cumulative Sum:

    • Prefix sum calculate karne ke liye cumulative sum lete hain prefix sum array ka.

  • Convert String to Array:

    • String s ko array of characters mein convert karte hain taaki modifications apply kar sake.

  • Apply Shifts to Characters:

    • Prefix sum array ka use kar ke har character ka net shift calculate karte hain.

    • Modulo 26 use kar ke shifts ko wrap around karte hain.

    • Har character ko new shifted character se replace karte hain.

  • Return Final String:

    • Sab shifts apply karne ke baad modified string s return karte hain.

Solution

				
					class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n = s.length(); // String ki length n hai
        vector<int> diff(n + 1, 0); // Difference array banate hain, initially 0 se fill

        for (const auto& shift : shifts) { // Har shift operation ke liye
            int start = shift[0], end = shift[1], direction = shift[2];
            int value = (direction == 1) ? 1 : -1; // Forward shift ke liye +1, backward ke liye -1
            diff[start] += value; // Starting index par value add karte hain
            diff[end + 1] -= value; // Ending index ke baad value subtract karte hain
        }

        vector<int> shiftsApplied(n, 0); // Shifts applied array banate hain, initially 0 se filled
        int cumulativeShift = 0; // Cumulative shift ko track karte hain

        for (int i = 0; i < n; ++i) { // Har character ke liye cumulative shift calculate karte hain
            cumulativeShift += diff[i]; // Cumulative sum lete hain
            shiftsApplied[i] = cumulativeShift; // Shifts applied array update karte hain
        }

        for (int i = 0; i < n; ++i) { // Har character par shift apply karte hain
            int shift = (s[i] - 'a' + shiftsApplied[i]) % 26; // Net shift calculate karte hain
            if (shift < 0) shift += 26; // Negative shift ko normalize karte hain
            s[i] = 'a' + shift; // Original character replace karte hain shifted character se
        }

        return s; // Final shifted string return karte hain
    }
};
    • String Length:

Pehle, original string s ki length n calculate karte hain.

Ā  Ā Difference Array Create:

Ek diff array banate hain jo initially zero se filled hota hai. Yeh array har shift operation ka effect store karta hai.

Ā  Ā Process Shifts:

Har shift operation ko process karte hain:

start aur end indices aur direction (forward ya backward) fetch karte hain.

value ko set karte hain: 1 for forward shift, aur -1 for backward shift.

diff[start] par value add karte hain aur diff[end + 1] par value subtract karte hain.

Ā  Ā Calculate Cumulative Sum:

Shifts applied array shiftsApplied ko fill karne ke liye cumulative sum lete hain diff array ka.

Cumulative shift ko track karte hain har index ke liye aur shiftsApplied array update karte hain.

Ā  Ā Apply Shifts:

shiftsApplied ki values use karke har character ka net shift calculate karte hain.

Negative shift ke liye, modulo operation ke sath wrap around karte hain.

Original character ko new shifted character se replace karte hain.

Ā  Ā Return Final String:

Finally, modified string s return karte hain jisme sab shifts applied hain.