Maximum Moves to Reach Destination Character in a Cyclic String in Java
In this tutorial, we are going to learn about the maximum moves to reach destination character in a cyclic string in java. Let S be a cyclic string of length N with just the three letters "a," "b," and "c." Two further characters are provided: the final character (fc) and the initial character (ic). The goal is to determine the greatest distance between an ic and its nearest fc.
Examples:
Example 1:
Input:
s = “caacb”, ic = ‘c’, fc = ‘a’
Output:0
3
Explanation:
There are two possibilities because the first character is "c" and the last character is "a": "a" will appear either immediately after one move (if we pick s[0] as ic) or after three moves (if we choose s[3] as ic). Consequently, the maximum number of moves that can be made to get from ic to fc is 3, which is the same as the solution.
Example 2:
Input:
s = “cccabbbab”, ic = ‘b’, fc = ‘a’
Output:
4
Approach: Using String Traversal with Position Tracking approach.
Step 1: Find the closest fc on the right for each cell of ic in the first half can be used to eliminate cyclicity. This allows us to write the string S twice and solve the cyclicity problem.
Step 2: Follow the line from right to left while keeping track of the latest instance of fc in the index.
Step 3: Update the response using the formula ans = max(ans, last – i) if we come across ic next.
Step 4: Where last is the nearest one that fc was traversed, and i is the current one.
Filename: Traversal.java
import java.io.*; public class Traversal { // Maximum possible moves to reach destination static int maxMoves(String s, char ic, char fc) { // Length of the string int n = s.length(); // To get rid of cyclicity s += s; // To store the answer int ans = 0, f = -1; // Corner Case if (ic == fc) { return 0; } // Traversing loop from backwards // and calculate accordingly for (int i = 2 * n - 1; i >= 0; i--) { if (s.charAt(i) == ic && f != -1) { ans = Math.max(ans, f - i); } if (s.charAt(i) == fc) { f = i; } } // Return the answer return ans; } public static void main(String[] args) { String s = "caacb"; char ic = 'c', fc = 'a'; // Function call System.out.print(maxMoves(s, ic, fc)); } }
Output:
3
Time complexity: The time complexity of the program is O(N).
Space complexity: The time complexity of the program is O(N) as we are concatenating the same string to itself