Given a string S representing a sequence of moves(L, R, U, and D) and two integers X and Y representing the starting coordinates, the task is to find the number of positions that are revisited while following the directions specified in the given string according to the following rules:
- If the current character is L, then decrement x-coordinate by 1.
- If the current character is R, then increment x-coordinate by 1.
- If the current character is U, then increment y-coordinate by 1.
- If the current character is D, then decrement y-coordinate by 1.
Examples:
Input: S = “RDDUDL”, X = 0, Y = 0
Output: 2
Explanation: Initially the coordinate is (0, 0). The change of coordinates according to the given order of traversal is as follows:
(0, 0) -> (1, 0) -> (1, -1) -> (1, -2) -> (1, -1) -> (1, -2) -> (0, -2)
Therefore, the number of times a coordinate is revisited is 2.Input: S = “RDDUDL”, X = 2, Y = 3
Output: 2
Approach: Follow the given steps to solve the problem:
- Initialize a HashSet of pairs that stores the pair of coordinates visited while traversing the given string and the current coordinates in the HashSet.
- Traverse the given string S and perform the following steps:
- After completing the above steps, print the value of the count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the number of times// already visited position is revisited// after starting traversal from {X, Y}int count(string S, int X, int Y){ int N = S.length(); // Stores the x and y temporarily int temp_x = 0, temp_y = 0; // Stores the number of times an // already visited position // is revisited int count = 0; // Initialize hashset set<pair<int, int> > s; // Insert the starting coordinates s.insert({ X, Y }); // Traverse over the string for (int i = 0; i < N; i++) { temp_x = X; temp_y = Y; // Update the coordinates according // to the current directions if (S[i] == 'U') { X++; } else if (S[i] == 'D') { X--; } else if (S[i] == 'R') { Y++; } else { Y--; } // If the new {X, Y} has been // visited before, then // increment the count by 1 if (s.find({ temp_x + X, temp_y + Y }) != s.end()) { count++; } // Otherwise else { // Insert new {x, y} s.insert({ temp_x + X, temp_y + Y }); } } return count;}// Driver Codeint main(){ string S = "RDDUDL"; int X = 0, Y = 0; cout << count(S, X, Y); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{ // Function to find the number of times // already visited position is revisited // after starting traversal from {X, Y} static int count(String S, int X, int Y) { int N = S.length(); // Stores the x and y temporarily int temp_x = 0, temp_y = 0; // Stores the number of times an // already visited position // is revisited int count = 0; // Initialize hashset HashSet<String> s = new HashSet<>(); // Insert the starting coordinates s.add((X + "#" + Y)); // Traverse over the string for (int i = 0; i < N; i++) { temp_x = X; temp_y = Y; // Update the coordinates according // to the current directions if (S.charAt(i) == 'U') { X++; } else if (S.charAt(i) == 'D') { X--; } else if (S.charAt(i) == 'R') { Y++; } else { Y--; } // If the new {X, Y} has been // visited before, then // increment the count by 1 if (s.contains((temp_x + X) + "#" + (temp_y + Y))) { count++; } // Otherwise else { // Insert new {x, y} s.add((temp_x + X) + "#" + (temp_y + Y)); } } return count; } // Driver Code public static void main(String[] args) { String S = "RDDUDL"; int X = 0, Y = 0; System.out.print(count(S, X, Y)); }}// This code is contributed by Kingash. |
Python3
# Python3 program for the above approach# Function to find the number of times# already visited position is revisited# after starting traversal from {X, Y}def count(S, X, Y): N = len(S) # Stores the x and y temporarily temp_x, temp_y = 0, 0 # Stores the number of times an # already visited position # is revisited count = 0 # Initialize hashset s = {} # Insert the starting coordinates s[(X, Y)] = 1 # Traverse over the string for i in range(N): temp_x = X temp_y = Y # Update the coordinates according # to the current directions if (S[i] == 'U'): X += 1 elif (S[i] == 'D'): X -= 1 elif (S[i] == 'R'): Y += 1 else: Y -= 1 # If the new {X, Y} has been # visited before, then # increment the count by 1 if ((temp_x + X, temp_y + Y ) in s): count += 1 # Otherwise else: # Insert new {x, y} s[(temp_x + X,temp_y + Y )] = 1 return count# Driver Codeif __name__ == '__main__': S = "RDDUDL" X,Y = 0, 0 print (count(S, X, Y)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the number of times // already visited position is revisited // after starting traversal from {X, Y} static int count(String S, int X, int Y) { int N = S.Length; // Stores the x and y temporarily int temp_x = 0, temp_y = 0; // Stores the number of times an // already visited position // is revisited int count = 0; // Initialize hashset HashSet<String> s = new HashSet<String>(); // Insert the starting coordinates s.Add((X + "#" + Y)); // Traverse over the string for (int i = 0; i < N; i++) { temp_x = X; temp_y = Y; // Update the coordinates according // to the current directions if (S[i] == 'U') { X++; } else if (S[i] == 'D') { X--; } else if (S[i] == 'R') { Y++; } else { Y--; } // If the new {X, Y} has been // visited before, then // increment the count by 1 if (s.Contains((temp_x + X) + "#" + (temp_y + Y))) { count++; } // Otherwise else { // Insert new {x, y} s.Add((temp_x + X) + "#" + (temp_y + Y)); } } return count; } // Driver Code public static void Main(String[] args) { String S = "RDDUDL"; int X = 0, Y = 0; Console.Write(count(S, X, Y)); }}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program for the above approach// Function to find the number of times// already visited position is revisited// after starting traversal from {X, Y}function count(S, X, Y){ let N = S.length; // Stores the x and y temporarily let temp_x = 0, temp_y = 0; // Stores the number of times an // already visited position // is revisited let count = 0; // Initialize hashset let s = new Set(); // Insert the starting coordinates s.add((X + "#" + Y)); // Traverse over the string for (let i = 0; i < N; i++) { temp_x = X; temp_y = Y; // Update the coordinates according // to the current directions if (S[i] == 'U') { X++; } else if (S[i] == 'D') { X--; } else if (S[i] == 'R') { Y++; } else { Y--; } // If the new {X, Y} has been // visited before, then // increment the count by 1 if (s.has((temp_x + X) + "#" + (temp_y + Y))) { count++; } // Otherwise else { // Insert new {x, y} s.add((temp_x + X) + "#" + (temp_y + Y)); } } return count;} // Driver Code let S = "RDDUDL"; let X = 0, Y = 0; document.write(count(S, X, Y)); </script> |
Output:
2
Time Complexity: O(N*log N)
Auxiliary Space: O(N)
Share your thoughts in the comments
