Count characters of a string which when removed individually makes the string equal to another string
Given two strings A and B of size N and M respectively, the task is to count characters of the string A, which when removed individually makes both the strings equal. If there exists several such characters, then print their respective positions. Otherwise, print “-1”.
Examples:
Input: A = “abaac”, B = “abac”
Output: 2
3 4
Explanation:
Following removals are possible that can make the strings equal:
- Removing A[2] modifies A to “abac”, which becomes equal to B.
- Removing A[3] modifies A to “abac”, which becomes equal to B.
Therefore, two possible removals satisfy the conditions.
Input: A = “abs”, B = “bkk”
Output: -1
Approach: The given problem can be solved based on the following observations:
- Suppose, if removing the character at index i, makes both strings equal then the prefix of the string i.e substring over the range [0, i-1] must be equal and the suffix of the string i.e substring over the range [i+1, N-1] must be equal too.
- Suppose i is the index satisfying that the substring over the range [0, i-1] is the longest equal prefix string. And j is the index satisfying that the substring over the range [j+1, N-1] is the longest equal suffix string
- Then, if i>=j then only, there exist characters removing which makes the both strings equal. And total count of such characters removing which individually makes the strings equal is i-j+1.
Follow the steps below to solve the problem:
- Initialize two variables say X as 0 and Y as N-1 to store the ending index of the longest equal prefix string and starting index of the longest equal suffix string.
- Iterate the over the characters of the string B and then in each iteration check if the current character is equal to the character at index X of the string A, then increment X by 1. Otherwise, break.
- Iterate the over the characters of the string B in reverse and then in each iteration check if the current character is equal to the character at index Y of the string A, then decrement Y by 1. Otherwise, break.
- Now if the difference between N and M is equal to 1 and Y is less than the X then:
- Print the total count of such characters as X-Y+1.
- Then print the indices of the character by iterating over the range [Y+1, X+1].
- Otherwise, print “-1”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count characters // from string A whose removal // makes the strings A and B equal void RemoveOneChar(string A, string B, int N, int M) { // Stores the index of // the longest prefix int X = 0; // Stores the index of // the longest suffix int Y = N - 1; // Traverse the string B for ( int i = 0; i < M; i++) { if (A[X] != B[i]) break ; X++; } // Traverse the string B for ( int i = M - 1; i >= 0; i--) { if (A[Y] != B[i]) break ; Y--; } // If N - M is equal to 1 and Y // is less than or equal to X if (N - M == 1 && Y < X) { // Print the count // of characters cout << X - Y + 1 << endl; // Print the positions // of the characters for ( int i = Y; i <= X; i++) cout << i + 1 << " " ; cout << endl; } // Otherwise else cout << -1 << endl; } // Driver Code int main() { string A = "abaac" ; string B = "abac" ; int N = A.length(); int M = B.length(); RemoveOneChar(A, B, N, M); } |
Java
// Java program for the above approach class GFG{ // Function to count characters // from string A whose removal // makes the strings A and B equal static void RemoveOneChar(String A, String B, int N, int M) { // Stores the index of // the longest prefix int X = 0 ; // Stores the index of // the longest suffix int Y = N - 1 ; // Traverse the string B for ( int i = 0 ; i < M; i++) { if (A.charAt(X) != B.charAt(i)) break ; X++; } // Traverse the string B for ( int i = M - 1 ; i >= 0 ; i--) { if (A.charAt(Y) != B.charAt(i)) break ; Y--; } // If N - M is equal to 1 and Y // is less than or equal to X if (N - M == 1 && Y < X) { // Print the count // of characters System.out.println(X - Y + 1 ); // Print the positions // of the characters for ( int i = Y; i <= X; i++) System.out.print(i + 1 + " " ); System.out.println(); } // Otherwise else System.out.println(- 1 ); } // Driver Code static public void main(String []args) { String A = "abaac" ; String B = "abac" ; int N = A.length(); int M = B.length(); RemoveOneChar(A, B, N, M); } } // This code is contributed by AnkThon |
Python3
# Python3 program for the above approach # Function to count characters # from A whose removal # makes the strings A and B equal def RemoveOneChar(A, B, N, M): # Stores the index of # the longest prefix X = 0 # Stores the index of # the longest suffix Y = N - 1 # Traverse the B for i in range (M): if (A[X] ! = B[i]): break X + = 1 # Traverse the B for i in range (M - 1 , - 1 , - 1 ): if (A[Y] ! = B[i]): break Y - = 1 # If N - M is equal to 1 and Y # is less than or equal to X if (N - M = = 1 and Y < X): # Print count # of characters print (X - Y + 1 ) # Print positions # of the characters for i in range (Y, X + 1 ): print (i + 1 , end = " " ) print () # Otherwise else : print ( - 1 ) # Driver Code if __name__ = = '__main__' : A = "abaac" B = "abac" N = len (A) M = len (B) RemoveOneChar(A, B, N, M) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; public class GFG{ // Function to count characters // from string A whose removal // makes the strings A and B equal static void RemoveOneChar( string A, string B, int N, int M) { // Stores the index of // the longest prefix int X = 0; // Stores the index of // the longest suffix int Y = N - 1; // Traverse the string B for ( int i = 0; i < M; i++) { if (A[X] != B[i]) break ; X++; } // Traverse the string B for ( int i = M - 1; i >= 0; i--) { if (A[Y] != B[i]) break ; Y--; } // If N - M is equal to 1 and Y // is less than or equal to X if (N - M == 1 && Y < X) { // Print the count // of characters Console.WriteLine(X - Y + 1); // Print the positions // of the characters for ( int i = Y; i <= X; i++) Console.Write(i + 1 + " " ); Console.WriteLine(); } // Otherwise else Console.WriteLine(-1) ; } // Driver Code static public void Main (){ string A = "abaac" ; string B = "abac" ; int N = A.Length; int M = B.Length; RemoveOneChar(A, B, N, M); } } // This code is contributed by AnkThon |
Javascript
<script> // JavaScript program for the above approach // Function to count characters // from string A whose removal // makes the strings A and B equal function RemoveOneChar(A, B, N, M) { // Stores the index of // the longest prefix var X = 0; // Stores the index of // the longest suffix var Y = N - 1; var i; // Traverse the string B for (i = 0; i < M; i++) { if (A[X] != B[i]) break ; X++; } // Traverse the string B for (i = M - 1; i >= 0; i--) { if (A[Y] != B[i]) break ; Y--; } // If N - M is equal to 1 and Y // is less than or equal to X if (N - M == 1 && Y < X) { // Print the count // of characters document.write(X - Y + 1 + "<br>" ); // Print the positions // of the characters for (i = Y; i <= X; i++) document.write(i + 1 + " " ); document.write( "\n" ); } // Otherwise else document.write(-1); } // Driver Code var A = "abaac" ; var B = "abac" ; var N = A.length; var M = B.length; RemoveOneChar(A, B, N, M); </script> |
Output:
2 3 4
Time Complexity: O(N)
Auxiliary Space: O(1)