Monday, February 6, 2023
HomeSoftware DevelopmentRemodel the given String into two identical Strings by eradicating at most...

Remodel the given String into two identical Strings by eradicating at most one character


Enhance Article

Save Article

Like Article

Enhance Article

Save Article

Given a string S of size N the place (N ≥ 1). The duty is to examine whether or not by eradicating at most one character from the given string it may be divided into two identical sub-strings or not return YES or NO for potentialities.

Examples:

Enter: N = 5, S = abzab
Output: YES
Clarification: Character ‘z’ at index 3 could be eliminated in order that the remaining S will likely be “abab”. Which consists of two identical sub-strings “ab” and “ab”. Therefor the output is YES. 

Enter: N = 4, S = abcd
Output: NO
Clarification: It may be verified {that a} given string can’t be divided into two sub-strings by eradicating at most one character from it.

Method: Comply with the under observations to resolve the issue:

Idea of method:

The issue is commentary based mostly and could be divided into followings components:

  • If S has size equal to 1:
    • On this case it’s unimaginable to make two equal strings.
  • If S has even size:
    • It needs to be famous that eradicating one character from even size will make the S string’s size equal to odd, Then we are able to’t divide odd size string S into two strings having the identical size. Formally, solely even size S could be divided into two strings. Subsequently, We will’t take away any character from even size String.
    • Simply divide the string into two halves and examine them utilizing in-built perform String. equals(String a, String b) of String class.
  • If S has odd size:    
    • It’s potential to make two sub-strings of equal size from odd size. For instance, S = “ababd”, Then it may be divided into two strings of wierd and even lengths as {“ab”, “bd”}, {“aba”, “abd”} respectively by eradicating one or zero character.
    • Then simply examine for each parity sub-strings individually, In the event that they differs by at most one character or not.   

Comply with the under steps to resolve the above method:

  • If the enter String has a size equal to 1.
    • Then it isn’t potential to make two equal strings.  
  • If the enter string has an even size
    • Then divide the enter string into two halves and examine in the event that they each are the identical or not utilizing the in-built String.equals(a, b) perform. 
  • If the enter string has an odd size  
    • Then divide the enter string into two odd and two even components and examine if there’s at most one totally different character, Then it’s potential else not potential.

Beneath is the Implementation of the above method:

Java

// Java code to implement the method

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

    // Operate to examine if there's at most
    // totally different character in strings given
    // as two arguements
    public static boolean examine(String a, String b)
    {
        int l = 0;
        int okay = 0;
        int countdiff = 0;
        whereas (l < a.size()) {
            if (okay < b.size()
                && a.charAt(l) == b.charAt(okay)) {
                l++;
                okay++;
            }
            else {
                l++;
                countdiff++;
            }
        }
        return countdiff <= 1;
    }

    // Driver perform
    public static void important(String args[])
    {

        // Enter N
        int N = 5;

        // Enter String
        String s = "ababz";

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

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

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

            // Seconf half sub-string
            String sec = s.substring((s.size() / 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 size of string is odd
        else {

            // 4 sub-strings as mentioned
            // in idea of method part
            String fir = s.substring(0, s.size() / 2 + 1);
            String sec = s.substring(s.size() / 2 + 1);
            String third = s.substring(s.size() / 2);
            String fourth = s.substring(0, s.size() / 2);

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

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

Associated Articles:

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments