ABHAY
BAN USER#include<bits/stdc++.h>
using namespace std;
int main(){
string s1,s2;
cin>>s1>>s2;
int l1=s1.length(),l2=s2.length();
int ans=INT_MAX;
if(l2>l1){
cout<<-1<<endl; // not possible
return 0;
}
for(int i=0 ; i<l1-l2+1 ; i++){
string temp=s1.substr(0,i)+s2+s1.substr(i+l2); // place s2 in all possible positions in s1
int cost=0;
// calculate cost to place s2
for(int j=i ; j<i+l2 ; j++){
if(s1[j]!=temp[j])
cost++;
}
int z=0;
// find the cost to convert new string to palindrome
for(int j=0 ; j<ceil(l1/2.0) ; j++){
if((j<i || j>=i+l2) && temp[j]!=temp[l1-j-1]) // if s2 is in the first half of new string
cost++;
else if(temp[j]!=temp[l1-j-1] && (l1-j-1<i || l1-j-1>=i+l2)) // if s2 is in the second half of new string
cost++;
else if(temp[j]!=temp[l1-j-1]){ // if s2 is in both halves
z=1;
break;
}
}
if(z==0)
ans=min(ans,cost);
}
if(ans==INT_MAX)
cout<<-1<<endl;
else
cout<<ans<<endl;
return 0;
}
package com.test.src;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class BallonBustingAlgo {
public static void main(String... args) {
List<Integer> sortedList = Arrays.asList(args[0].split("")).stream().map(str -> Integer.parseInt(str.trim()))
.sorted((i1, i2) -> i2.compareTo(i1)).collect(Collectors.toList());
Integer noOfArrows = countArrowsToBurstBalloons(sortedList, 0);
System.out.println(noOfArrows);
}
public static Integer countArrowsToBurstBalloons(List<Integer> bList, Integer noOfArrows) {
if (bList == null || bList.isEmpty())
return noOfArrows;
noOfArrows++;
// burst 1st balloon
bList.remove(0);
bList = bList.stream().map(ballon -> {
if (ballon > 1)
return ballon - 1;
else
return null;
}).filter(ballon -> ballon != null).collect(Collectors.toList());
return countArrowsToBurstBalloons(bList, noOfArrows);
}
}
package com.test.src;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class BallonBustingAlgo {
public static void main(String... args) {
List<Integer> sortedList = Arrays.asList(args[0].split("")).stream().map(str -> Integer.parseInt(str.trim()))
.sorted((i1, i2) -> i2.compareTo(i1)).collect(Collectors.toList());
Integer noOfArrows = countArrowsToBurstBalloons(sortedList, 0);
System.out.println(noOfArrows);
}
public static Integer countArrowsToBurstBalloons(List<Integer> bList, Integer noOfArrows) {
if (bList == null || bList.isEmpty())
return noOfArrows;
noOfArrows++;
// burst 1st balloon
bList.remove(0);
bList = bList.stream().map(ballon -> {
if (ballon > 1)
return ballon - 1;
else
return null;
}).filter(ballon -> ballon != null).collect(Collectors.toList());
return countArrowsToBurstBalloons(bList, noOfArrows);
}
}
SPACE: N^2
COMPLEXITY: N^2
- ABHAY August 19, 2019