Check if it is possible to go from one point to another by choosing a Subsequence of steps of smallest length
Given a string S of characters R, L, U, D, along with integers X1, Y1, X2, Y2. In String S, ‘R’, ‘L’, ‘U’, and’D’ denote right, left, up, and down steps from the current position. Then the task is to output the length of the smallest length subsequence of steps from S, such that following those steps we can reach from (X1, Y1) to (X2, Y2). If it is not possible just output NO.
Examples:
Input: S = RLRRLLUUDU, X1 = 1, Y1 =1, X2 = 2, Y2 = 4
Output: YES 4
Explanation: The initial position is (X1, Y1) = (1, 1), We can reach to (X2, Y2) = (2, 4) by using the sub-sequence RUUU(RLRRLLUUDU). It can be verified that it is the smallest length subsequence following what we can reach from (X1, Y1) to (X2, Y2). The length of the sub-sequence is 4. Therefore, the output is 4.Input: S = UDLLU, X1 = 2, Y1 =1, X2 = 3, Y2 = 1
Output: NO
Explanation: It can be verified that no subsequence is there such that following which we can reach from (2, 1) to (3, 1).
Approach: Follow the idea below to solve the problem
- The problem is observation based and can be solved by using those observations implemented by a code. First of all we need to count the total number of steps available in S, So traverse the string and count the steps Right, left, up, down in the variables let say R, L, U and D.
- Then count the number of steps needed to reach from (X1, Y1) to (X2, Y2) in the variables Right, Left, Up and Down as (X2 – X1), (X1 – X2), (Y2 – Y1) and (Y1 – Y2) respectively.
- It should be noted that if condition (Right – R > 0 || Left – L > 0 || Up – U > 0 || Down – D > 0) proves true then there will not exist any subsequence following which we can go from (X1, Y1), to (X2, Y2). Otherwise It can be observed that, If any shortest subsequence of steps exist, Then it will be equal to (Right + Left + Up + Down).
Steps to be taken to solve the problem:
- Create variables R, L, U, and D and count the frequency of steps into these variables.
- Create variables Right, Left, Up, and Down and initialize them with ( X2 – X1 ), ( X1 – X2 ), ( Y2 – Y1 ), and ( Y1 – Y2 ) respectively.
- Create a variable Diff and initialize it with ( Right + Left + Up + Down ).
- If (Right – R > 0 || Left – L > 0 || Up – U > 0 || Down – D > 0) then output NO else YES.
Below is the code to implement the approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Method for checking the possibility // and printing output void isPossible(string s, int x1, int y1, int x2, int y2) { // Variables for storing // counts of steps int r = 0, l = 0, u = 0, d = 0; // Loop for initializing variables for ( int i = 0; i < s.length(); i++) { if (s[i] == 'R' ) r++; else if (s[i] == 'L' ) l++; else if (s[i] == 'U' ) u++; else if (s[i] == 'D' ) d++; } // Implementing approach int right = 0, left = 0, up = 0, down = 0; if (x2 - x1 > 0) { right = x2 - x1; } else if (x2 < x1) { left = x1 - x2; } if (y2 - y1 > 0) { up = y2 - y1; } else if (y2 - y1 < 0) { down = y1 - y2; } int diff = right + left + up + down; // Printing output based on the // conditions if (right - r > 0 || left - l > 0 || up - u > 0 || down - d > 0) { cout << "NO\n" ; } else { cout << "YES " << diff << "\n" ; } } int main() { // Inputs string s = "RLRRLLUUDU" ; int x1 = 1; int y1 = 1; int x2 = 2; int y2 = 4; // Function call isPossible(s, x1, y1, x2, y2); } |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Driver Function public static void main(String[] args) throws IOException { // Inputs String s = "RLRRLLUUDU" ; int x1 = 1 ; int y1 = 1 ; int x2 = 2 ; int y2 = 4 ; // Function call isPossible(s, x1, y1, x2, y2); } // Method for checking the possibility // and printing output static void isPossible(String s, int x1, int y1, int x2, int y2) { // Variables for storing // counts of steps int r = 0 , l = 0 , u = 0 , d = 0 ; // Loop for initializing // variables for ( int i = 0 ; i < s.length(); i++) { if (s.charAt(i) == 'R' ) r++; else if (s.charAt(i) == 'L' ) l++; else if (s.charAt(i) == 'U' ) u++; else if (s.charAt(i) == 'D' ) d++; } // Implementing approach int right = 0 , left = 0 , up = 0 , down = 0 ; if (x2 - x1 > 0 ) { right = x2 - x1; } else if (x2 < x1) { left = x1 - x2; } if (y2 - y1 > 0 ) { up = y2 - y1; } else if (y2 - y1 < 0 ) { down = y1 - y2; } int diff = right + left + up + down; // Printing output based on the // conditions if (right - r > 0 || left - l > 0 || up - u > 0 || down - d > 0 ) { System.out.print( "NO\n" ); } else { System.out.print( "YES " + diff + "\n" ); } } } |
Python
# Method for checking the possibility # and printing output def isPossible(s, x1, y1, x2, y2): # Variables for storing # counts of steps r = 0 l = 0 u = 0 d = 0 # Loop for initializing variables for i in range ( len (s)): if s[i] = = 'R' : r + = 1 elif s[i] = = 'L' : l + = 1 elif s[i] = = 'U' : u + = 1 elif s[i] = = 'D' : d + = 1 # Implementing approach right = 0 left = 0 up = 0 down = 0 if x2 - x1 > 0 : right = x2 - x1 elif x2 < x1: left = x1 - x2 if y2 - y1 > 0 : up = y2 - y1 elif y2 - y1 < 0 : down = y1 - y2 diff = right + left + up + down # Printing output based on the # conditions if right - r > 0 or left - l > 0 or up - u > 0 or down - d > 0 : print ( "NO" ) else : print ( "YES " + str (diff)) # Inputs s = "RLRRLLUUDU" x1 = 1 y1 = 1 x2 = 2 y2 = 4 # Function call isPossible(s, x1, y1, x2, y2) #This code is contributed by NarasingaNikhil |
C#
// C# code to implement the approach using System; public class GFG{ // Method for checking the possibility // and printing output static void isPossible( string s, int x1, int y1, int x2, int y2) { // Variables for storing // counts of steps int r = 0, l = 0, u = 0, d = 0; // Loop for initializing // variables for ( int i = 0; i < s.Length; i++) { if (s[i] == 'R' ) r++; else if (s[i] == 'L' ) l++; else if (s[i] == 'U' ) u++; else if (s[i] == 'D' ) d++; } // Implementing approach int right = 0, left = 0, up = 0, down = 0; if (x2 - x1 > 0) { right = x2 - x1; } else if (x2 < x1) { left = x1 - x2; } if (y2 - y1 > 0) { up = y2 - y1; } else if (y2 - y1 < 0) { down = y1 - y2; } int diff = right + left + up + down; // Printing output based on the // conditions if (right - r > 0 || left - l > 0 || up - u > 0 || down - d > 0) { Console.WriteLine( "NO\n" ); } else { Console.WriteLine( "YES " + diff + "\n" ); } } // Driver Function static public void Main (){ string s = "RLRRLLUUDU" ; int x1 = 1; int y1 = 1; int x2 = 2; int y2 = 4; // Function call isPossible(s, x1, y1, x2, y2); } } |
Javascript
// JavaScript code to implement the approach function isPossible(s, x1, y1, x2, y2) { // Variables for storing counts of steps let r = 0, l = 0, u = 0, d = 0; // Loop for initializing variables for (let i = 0; i < s.length; i++) { if (s[i] == 'R' ) r++; else if (s[i] == 'L' ) l++; else if (s[i] == 'U' ) u++; else if (s[i] == 'D' ) d++; } // Implementing approach let right = 0, left = 0, up = 0, down = 0; if (x2 - x1 > 0) { right = x2 - x1; } else if (x2 < x1) { left = x1 - x2; } if (y2 - y1 > 0) { up = y2 - y1; } else if (y2 - y1 < 0) { down = y1 - y2; } let diff = right + left + up + down; // Printing output based on the conditions if (right - r > 0 || left - l > 0 || up - u > 0 || down - d > 0) { console.log( "NO" ); } else { console.log( "YES " + diff); } } // Inputs let s = "RLRRLLUUDU" ; let x1 = 1; let y1 = 1; let x2 = 2; let y2 = 4; // Function call isPossible(s, x1, y1, x2, y2); |
YES 4
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us