Check if string S can be converted to T by incrementing characters in Java
Given two equal-length strings S and T and a positive integer K, find if string S can be transformed into string T by cyclically incrementing characters by at most K units. Furthermore, guarantee that each character transformation from S to T takes no more than K increments.
Note: Each increment is cyclic, so 'z' incremented by 1 becomes 'a'.
Example:
Input: S = xyz, T = yza; K = 2
Output: No, it is not possible to convert S to T.
Explanation:
The total number of needed increments exceeds the maximum permitted (K = 2). As a result, the string S cannot be converted to T within the limitations specified.
Shift-Based Character Mapping Approach
Step 1: Determine whether the strings S and T lengths are equal; if not, return false.
Step 2: Create an array arr[] of size 26 to contain shift frequencies.
Step 3: Iterate through each character in strings S and T, calculating the shift required to turn each character in S into its matching character in T.
Step 4: Determine whether the total number of shifts required for any character exceeds the limit K. If so, return false.
Step 5: Track the frequency of shifts for each character.
Step 6: If all of the characters can be transformed within the limit, return true.
FileName: StringConversionPossibilityChecker.java
import java.io.*; public class StringConversionPossibilityChecker { // Function to check if conversion is possible public static boolean canConvert(String S, String T, int K) { // Check if the size of both strings is not equal, return false if (S.length() != T.length()) return false; // Initialize an array of size 26 // where, arr[i] = x implies that // there are x characters in string S // that need a shift of i times to // match the characters in string T. int arr[] = new int[26]; // Iterate over the string S. for (int i = 0; i < S.length(); i++) { // Calculate the increment needed to convert S[i] to T[i] int shift = (T.charAt(i) - S.charAt(i) + 26) % 26; // Calculate the total operations required to increment all elements // requiring the same number of increments. If total operations required // is greater than K, return false if (shift != 0 && shift + arr[shift] * 26 > K) return false; // Increment the frequency of shift in array arr arr[shift]++; } // Finally, return true return true; } // Driver Code public static void main(String[] args) { String S = "xyz"; String T = "yza"; int K = 2; // Function Call if (canConvert(S, T, K)) System.out.println("Yes, it is possible to convert S to T."); else System.out.println("No, it is not possible to convert S to T."); } }
Output:
No, it is not possible to convert S to T.
Complexity Analysis: The code has a time complexity of O(n) and a space complexity of O(1), where 'n' represents the length of the input strings S and T.
String Manipulation Approach
Step 1: Check whether strings S and T lengths are equal. If not, return False.
Step 2: Create an array freq of size 26 to store the frequency of characters.
Step 3: Traverse each character in both strings S and T at the same time.
Step 4: Determine the character difference between the respective locations in strings S and T. To accommodate wrapping around the alphabet, calculate the difference modulo 26.
Step 5: If the difference is non-zero and the number of operations needed to transform the character exceeds K, return false.
Step 6: Update the frequency array with the determined difference.
Step 7: Return true if all characters were successfully processed without violating the operations constraint.
FileName: StringConversionPossibilityChecker1.java
import java.util.Arrays; public class StringConversionPossibilityChecker1 { static boolean canSToT(String S, String T, int K) { // Compare sizes if (S.length() != T.length()) return false; // To store the frequency of characters int[] freq = new int[26]; Arrays.fill(freq, 0); // Traverse string S for (int p = 0; p < S.length(); p++) { // Calculating the required increment int diff = (T.charAt(p) - S.charAt(p) + 26) % 26; // To increment freq[diff] characters, we need minimum diff + freq[diff]*26 operations if (diff != 0 && diff + freq[diff] * 26 > K) return false; // Update character frequency freq[diff]++; } // Final answer return true; } public static void main(String[] args) { String S = "xyz", T = "yza"; int K = 2; if (canSToT(S, T, K)) System.out.println("Yes, it is possible to convert S to T."); else System.out.println("No, it is not possible to convert S to T."); } }
Output:
No, it is not possible to convert S to T.
Complexity Analysis: The code has a time complexity of O(n) and a space complexity of O(1), where 'n' represents the length of the input strings S and T.