CODEWITHSUNDEEP
stringalgorithm
Vinod
Vinod

Reputation: 294

Get Palindrome of a String with replacement

Elina has a string S, consisting of lowercase English alphabetic letters(ie. a-z). She can replace any character in the string with any other character, and she can perform this replacement any number of times. she wants to create a palindromic string, p , from s such that string p contains the sub string linkedin . it is guaranteed that Elina can create palindromic string p from S. find the minimum number of operation required to create palindromic string p from S. Sample test case are:

First test case: S="linkedininininin"

explanation : 

            linkedin (i) (n) (i) (n) (i) ni (n)

                     (n) (i) (d) (e) (k)    (l)  

            p =  "linkedinnideknil"

output is 6

Second test case: S="fulrokxeuolnzxltiiniabudyyozvulqbydmaldbxaddmkobhlplkaplgndnksqidkaenxdacqtsskdkdddls"

output is 46

here i was unable to get second test case output, how it's getting output 46.

Third Test Case: 

              S="linkaeiouideknil"

              P="linkedinnideknil" 
    Output = 4

Upvotes: 0

Views: 1797

Answers (1)

Rohit Katariya
Rohit Katariya

Reputation: 167

Here is code with time complexity of O(n).

import java.io.*;
import java.util.*;

class TestClass {
    public static void main(String args[] ) throws Exception {
     Scanner sc = new Scanner(System.in);
     String input = sc.next();
     String ln = "linkedin";
     String rln= "nideknil";
     int limit, limit2;
     int len = input.length(); 

  if(len%2==0){
      limit=len/2-7;
      limit2=len/2-1;
  }else{
      limit=(len+1)/2-7;
      limit2= (len-1)/2 -1;
  }
  int max=0,index=0;
 boolean  rev=false;
  for(int i = 0; i<=len-8;i++){
       int count1=0, count2=0;

      if(i==limit){
          if(len%2==0){
              i=len/2;

          }else{
              i=(len-1)/2;
          }

      }

     String temp=input.substring(i,i+8);

      for(int j=0;j<8;j++){
          if(ln.charAt(j)==temp.charAt(j)){
              count1++;
          }
          if(rln.charAt(j)==temp.charAt(j)){
              count2++;
          }
          int temp2 = count1 > count2 ? count1 : count2;

          if(temp2>max){
              index=i;
              max=temp2;
              if(temp2==count2){
                  rev=true;
              }
              else 
              rev=false;
          }

      }
  }

  int replace=0;
  char in[]= input.toCharArray();
  int i,j;

  for(i= index,j=0;i<index+8;j++,i++){
   if(rev){
       if(rln.charAt(j)!=in[i]){
           replace++;

           in[i]=rln.charAt(j);
       }
   } else{
        if(ln.charAt(j)!=in[i]){
           replace++;

           in[i]=ln.charAt(j);
       }
     }  
  }

     for(j=0,i = len-1; j<=limit2 ;i--,j++){
        if(in[i]!=in[j]){
            replace++;
        }
   }


       System.out.println(replace);
    }
 }

Upvotes: 1

Related Questions