Transform the given String into two same Strings by removing at most one character

Given a string S of length N where (N ≥ 1). The task is to check whether by removing at most one character from the given string it can be divided into two same sub-strings or not return YES or NO for possibilities.

Examples:

Input: N = 5, S = abzab
Output: YES
Explanation: Character ‘z’ at index 3 can be removed so that the remaining S will be “abab”. Which consists of two same sub-strings “ab” and “ab”. Therefor the output is YES. 

Input: N = 4, S = abcd
Output: NO
Explanation: It can be verified that a given string can’t be divided into two sub-strings by removing at most one character from it.

Approach: Follow the below observations to solve the problem:

Concept of approach:

The problem is observation based and can be divided into followings parts:

• If S has length equal to 1:
  • In this case it is impossible to make two equal strings.
• If S has even length:
  • It should be noted that removing one character from even length will make the S string’s length equal to odd, Then we can’t divide odd length string S into two strings having the same length. Formally, only even length S can be divided into two strings. Therefore, We can’t remove any character from even length String.
  • Just divide the string into two halves and compare them using in-built function String. equals(String a, String b) of String class.
• If S has odd length:    
  • It is possible to make two sub-strings of equal length from odd length. For example, S = “ababd”, Then it can be divided into two strings of odd and even lengths as {“ab”, “bd”}, {“aba”, “abd”} respectively by removing one or zero character.
  • Then just check for both parity sub-strings separately, If they differs by at most one character or not.   

Follow the below steps to solve the above approach:

• If the input String has a length equal to 1.
  • Then it is not possible to make two equal strings.  
• If the input string has an even length
  • Then divide the input string into two halves and check if they both are the same or not using the in-built String.equals(a, b) function. 
• If the input string has an odd length  
  • Then divide the input string into two odd and two even parts and compare if there is at most one different character, Then it is possible else not possible.

Below is the Implementation of the above approach:

// Java code to implement the approach

import java.io.*;
import java.math.*;
import java.util.*;
public class GFG {

    // Function to check if there is at most
    // different character in strings given
    // as two arguements
    public static boolean check(String a, String b)
    {
        int l = 0;
        int k = 0;
        int countdiff = 0;
        while (l < a.length()) {
            if (k < b.length()
                && a.charAt(l) == b.charAt(k)) {
                l++;
                k++;
            }
            else {
                l++;
                countdiff++;
            }
        }
        return countdiff <= 1;
    }

    // Driver function
    public static void main(String args[])
    {

        // Input N
        int N = 5;

        // Input String
        String s = "ababz";

        // If length of string is 1
        if (s.length() == 1) {
            System.out.println("NO");
        }

        // If length of string is even
        else if (s.length() % 2 == 0) {

            // First half sub-string
            String fir = s.substring(0, (s.length() / 2));

            // Seconf half sub-string
            String sec = s.substring((s.length() / 2));

            // If first and second are equals
            // then printing YES
            if (fir.equals(sec)) {
                System.out.println("YES");
            }

            // Else printing NO
            else {
                System.out.println("NO");
            }
        }

        // If length of string is odd
        else {

            // Four sub-strings as discussed
            // in concept of approach section
            String fir = s.substring(0, s.length() / 2 + 1);
            String sec = s.substring(s.length() / 2 + 1);
            String third = s.substring(s.length() / 2);
            String fourth = s.substring(0, s.length() / 2);

            // Checking using user-defined
            // function that sub-strings differs
            // by at most one characters or not.
            if (check(fir, sec) || check(third, fourth)) {
                System.out.println("YES");
            }
            else {
                System.out.println("NO");
            }
        }
    }
}

Time Complexity: O(N)
Auxiliary Space: O(1)

Related Articles: