Given a string S of length n representing n boxes adjacent to each other.
- A character R at index i represents that i-th box is being pushed towards the right.
- On the other hand, L at index i represents that i-th box is being pushed towards the left.
- And a . represents an empty space.
We start with initial configuration, at every time unit, a box being pushed toward right pushes next box toward right and same is true for a box being pushed toward left. The task is to print the final positions of all boxes when no more movements are possible. If there is a substring “R.L”, then middle box is being pushed from both directions and therefore not moved any more.
Examples:
Input: S = “RR.L”
Output: RR.L
The first and second boxes are being toward right. The middle dot is being pushed from both directions, so does not move.Input: S = “R..R…L.”
Output: RRRRR.LL.
At time unit 1 :
The first box pushes second box.
Third box pushes fourth box.
Second last box pushes third last box, configuration becomes
“RR.RR.LL.”
At time unit 2 :
Second box pushes third box, string becomes
“RRRRR.LL.”
Approach: We can calculate the net force applied on every box. The forces we care about are how close a box is to a leftward R or to a rightward L i.e. the more closer we are, the stronger will be the force.
- Scanning from left to right, force decays by 1 in every iteration, and resets to N if we meet an R again.
- Similarly, from right to left direction, we can find the forces from the right (closeness to L).
- For some box result[i], if the forces are equal then the result is . as both side apply same force to it. Otherwise, our result is implied by whichever force is stronger.
For string S = “R..R…L.”
The forces going from left to right are [7, 6, 5, 7, 6, 5, 4, 0, 0].
The forces going from right to left are [0, 0, 0, 0, -4, -5, -6, -7, 0].
Combining them (taking their arithmetic addition at each index) gives result = [7, 6, 5, 7, 2, 0, -2, -7, 0].
Thus, the final answer is RRRRR.LL.
Below is the implementation of above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to return final// positions of the boxesstring pushBoxes(string S) { int N = S.length(); vector<int> force(N, 0); // Populate forces going // from left to right int f = 0; for(int i = 0; i < N; i++) { if (S[i] == 'R') { f = N; } else if (S[i] == 'L') { f = 0; } else { f = max(f - 1, 0); } force[i] += f; } // Populate forces going from right to left f = 0; for(int i = N - 1; i >= 0; i--) { if (S[i] == 'L') { f = N; } else if (S[i] == 'R') { f = 0; } else { f = max(f - 1, 0); } force[i] -= f; } // return final state of boxes string ans; for(int f : force) { ans += f == 0 ? '.' : f > 0 ? 'R' : 'L'; } return ans;}// Driver codeint main() { string S = ".L.R...LR..L.."; // Function call to print answer cout << pushBoxes(S);}// This code is contributed by sanjeev2552 |
Java
// Java implementation of above approachimport java.util.*;class GFG { // Function to return final // positions of the boxes static String pushBoxes(String S) { int N = S.length(); int[] force = new int[N]; for (int i = 0; i < N; i++) force[i] = 0; // Populate forces going // from left to right int f = 0; for (int i = 0; i < N; i++) { if (S.charAt(i) == 'R') { f = N; } else if (S.charAt(i) == 'L') { f = 0; } else { f = Math.max(f - 1, 0); } force[i] += f; } // Populate forces going from right to left f = 0; for (int i = N - 1; i >= 0; i--) { if (S.charAt(i) == 'L') { f = N; } else if (S.charAt(i) == 'R') { f = 0; } else { f = Math.max(f - 1, 0); } force[i] -= f; } // return final state of boxes String ans = ""; for (int f1 : force) { ans += f1 == 0 ? '.' : f1 > 0 ? 'R' : 'L'; } return ans; } // Driver code public static void main(String[] args) { String S = ".L.R...LR..L.."; // Function call to print answer System.out.println(pushBoxes(S)); }}// This code is contributed by phasing17 |
Python3
# Python3 implementation of above approach# Function to return final # positions of the boxesdef pushBoxes(S): N = len(S) force = [0] * N # Populate forces going from left to right f = 0 for i in range(0, N): if S[i] == 'R': f = N elif S[i] == 'L': f = 0 else: f = max(f - 1, 0) force[i] += f # Populate forces going from right to left f = 0 for i in range(N - 1, -1, -1): if S[i] == 'L': f = N elif S[i] == 'R': f = 0 else: f = max(f - 1, 0) force[i] -= f # return final state of boxes return "".join('.' if f == 0 else 'R' if f > 0 else 'L' for f in force)# Driver codeS = ".L.R...LR..L.."# Function call to print answerprint(pushBoxes(S)) |
C#
// C# implementation of above approachusing System;using System.Collections.Generic;class GFG{ // Function to return final // positions of the boxes static string pushBoxes(string S) { int N = S.Length; List<int> force = new List<int>(); for (int i = 0; i < N; i++) force.Add(0); // Populate forces going // from left to right int f = 0; for (int i = 0; i < N; i++) { if (S[i] == 'R') { f = N; } else if (S[i] == 'L') { f = 0; } else { f = Math.Max(f - 1, 0); } force[i] += f; } // Populate forces going from right to left f = 0; for (int i = N - 1; i >= 0; i--) { if (S[i] == 'L') { f = N; } else if (S[i] == 'R') { f = 0; } else { f = Math.Max(f - 1, 0); } force[i] -= f; } // return final state of boxes string ans = ""; foreach(int f1 in force) { ans += f1 == 0 ? '.' : f1 > 0 ? 'R' : 'L'; } return ans; } // Driver code public static void Main(string[] args) { string S = ".L.R...LR..L.."; // Function call to print answer Console.WriteLine(pushBoxes(S)); }}// This code is contributed by phasing17 |
Javascript
// JavaScript implementation of above approach// Function to return final// positions of the boxesfunction pushBoxes(S) { let N = S.length; let force = new Array(N).fill(0); // Populate forces going // from left to right let f = 0; for(let i = 0; i < N; i++) { if (S[i] == 'R') { f = N; } else if (S[i] == 'L') { f = 0; } else { f = Math.max(f - 1, 0); } force[i] += f; } // Populate forces going from right to left f = 0; for(let i = N - 1; i >= 0; i--) { if (S[i] == 'L') { f = N; } else if (S[i] == 'R') { f = 0; } else { f = Math.max(f - 1, 0); } force[i] -= f; } // return final state of boxes let ans = ""; for(f of force) { ans += f == 0 ? '.' : f > 0 ? 'R' : 'L'; } return ans;}// Driver codelet S = ".L.R...LR..L.."; // Function call to print answerconsole.log(pushBoxes(S));// This code is contributed by sanjeev2552 |
LL.RR.LLRRLL..
ComplexityAnalysis:
- Time Complexity: O(N)
- Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
