Hackerrank Interview Question
Software Engineer InternsCountry: India
Interview Type: Written Test
Here a solution in Swift:
func shrinkString(var string: String, substrings: String[]) -> String {
for substring in substrings {
if !string.rangeOfString(substring).isEmpty {
string = string.stringByReplacingOccurrencesOfString(substring, withString: "")
string = shrinkString(string, substrings);
}
}
return string;
}
The solution below does the work in space.
it uses:
hashing,
replacing them with zeros and then concatenates.
The algorithms assumes the substrings are of equal length
int hashfunc( char *str , int len ) {
int hash = 0, k = 0;
while ( *str && k++ < len ) {
hash = ((hash << 1 ) + hash ) + int(*str++);
}
return hash;
}
void mystrcat( char *dst, char *src ) {
while ( *src ) *dst++ = *src++;
while ( *dst ) *dst++ = '\0';
}
void stringDeletion(char *str, char *s1, char *s2) {
char * temp = str;
int hashValue1 = 0, hashValue2 = 0, hashValueStr = 0, len1 = 0, len2 = 0, hashing = 0;
while ( *s1 ) {
len1++; s1++;
}
hashValue1 = hashfunc ( s1-len1, len1 );
while ( *s2 ) {
len2++; s2++;
}
hashValue2 = hashfunc ( s2-len2, len2 );
while ( *str ) {
if ( *str == '0' ) {
char *temp = str;
while ( *temp == '0' ) temp++;
mystrcat(str, temp);
hashing++;
}
hashValueStr = hashfunc ( str, len1 );
if ( hashValueStr == hashValue1 ) {
hashing++;
for ( int i = 0; i < len1; i++ ) *str++ = '0';
}
else if ( hashValueStr == hashValue2 ) {
hashing++;
for ( int i = 0; i < len2; i++ ) *str++ = '0';
}
else str++;
if ( *str == '\0' && hashing > 0 ) {
hashing = 0;
str = temp;
}
}
cout << "Modified length is: " << strlen(temp) << endl;
cout << "Modified string is: " << temp << endl;
}
Using Java, replaceAll and regular expressions
private int replaceStrings(String a, Set<String> strings) {
if (a == null) {
throw new IllegalArgumentException("One of the arguments was null");
} else if (strings == null) {
return a;
}
String newString = a;
String oldString = null;
StringBuilder builder = new StringBuilder();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()) {
builder.append(iterator.next()).append("|");
}
builder.deleteCharAt(builder.length() - 1);
while (!newString.equals(oldString)) {
oldString = newString;
newString = newString.replaceAll(builder.toString(), "");
}
return newString.length();
}
public int removeSub(String target, HashSet <String> set) {
if (target.length() == 0) {
return 0 ;
}
Stack<Character> stack = new Stack<Character>();
char [] chs = target.toCharArray() ;
for (int i = 0 ; i < chs.length ; ++i) {
if (stack.isEmpty()) {
stack.push(chs[i]);
continue;
}
StringBuilder sub = new StringBuilder ();
sub.append(stack.peek()) ;
sub.append(chs[i]) ;
if (set.contains(sub.toString())) {
stack.pop() ;
} else {
stack.push(chs[i]) ;
}
sub.setLength(0) ;
}
return stack.size() ;
}
class Program
{
static void Main(string[] args)
{
string target = "ccdaabcdbb";
HashSet<string> patterns = new HashSet<string>();
patterns.Add("ab");
patterns.Add("cd");
Console.WriteLine(findMinLengthString(target, 0, patterns));
Console.ReadKey();
}
static string findMinLengthString(string target, int startIndex, HashSet<string> patterns)
{
if (string.IsNullOrEmpty(target))
{
return string.Empty;
}
if (patterns == null && patterns.Count == 0)
{
return target;
}
if (startIndex == target.Length - 1)
{
return patterns.Contains(target.ElementAt(startIndex).ToString()) ? string.Empty : target.ElementAt(startIndex).ToString();
}
string shortest = findMinLengthString(target, startIndex + 1, patterns);
string possibleShortest = target.ElementAt(startIndex) + shortest;
string currentMaxPattern = string.Empty;
foreach (string pattern in patterns)
{
if (possibleShortest.Contains(pattern) && pattern.Length > currentMaxPattern.Length)
{
currentMaxPattern = pattern;
}
}
if (!string.IsNullOrEmpty(currentMaxPattern))
{
possibleShortest = possibleShortest.Replace(currentMaxPattern, string.Empty);
}
string secondPossibleShort = target.Substring(startIndex);
if (!string.IsNullOrEmpty(currentMaxPattern))
{
secondPossibleShort = secondPossibleShort.Replace(currentMaxPattern, string.Empty);
}
if (secondPossibleShort.Length > possibleShortest.Length)
{
return possibleShortest;
}
return secondPossibleShort;
}
As always the algo is not that important, the important part is finding the edge cases and unclear specifications.
Gotchas
1)Some substrings may intersect, for example "ab" and "bcd". Given a source string "abcd" the solution is "a" however most of the code in the answers here above will give the solution "cd".
Clarifications:
1) Do we remove only the substings that are present in the original string or those modified too? Given the substring "ab" and source "aabb" do we end up with "ab" or ""?
2) Do we remove several strings at once if they intersect? For the example given above of "abcd" can we remove "abc" and "cd" at the same time?
So the implementation should be recursive and should explore each substring and each substring occurence.
Here's my solution (in c#, framework 4.5):
This example will give 1 as output
const string initialString = "abcd";
var substringList = new List<string> {"ab","bcd"};
substringList = new List<string>(substringList.OrderByDescending(x => x.Length));
var newS = initialString;
while (substringList.Exists(newS.Contains))
{
substringList.ForEach(x=> newS = newS.Replace(x, string.Empty));
}
Console.WriteLine(newS.Length);
public static int getStr(String target,String[] srch)
{
String tempstr=target;
boolean found=true;
while(found)
{
for (String str : srch) {
if(tempstr.contains(str))
{
int idx=tempstr.indexOf(str);
tempstr=tempstr.substring(0,idx)+tempstr.substring(str.length()+idx, tempstr.length());
found=true;
//System.out.println(tempstr);
break;
}
found=false;
}
}
System.out.println(tempstr);
return tempstr.length();
}
public static int getStr(String target,String[] srch)
{
String tempstr=target;
boolean found=true;
while(found)
{
for (String str : srch) {
if(tempstr.contains(str))
{
int idx=tempstr.indexOf(str);
tempstr=tempstr.substring(0,idx)+tempstr.substring(str.length()+idx, tempstr.length());
found=true;
//System.out.println(tempstr);
break;
}
found=false;
}
}
System.out.println(tempstr);
return tempstr.length();
}
import java.util.Scanner;
class samp
{
private static Scanner scan;
private String mini(String s1,String[]s2)
{
StringBuilder bu = new StringBuilder();
String sb[]=null;
int k=s1.length();
while(k>0 )
{
for(int i=0;i<s2.length;i++)
{
sb=s1.split(s2[i], s2[i].length());
for(int j=0;j<sb.length;j++)
{
s1=sb[j];
bu.append(s1);
s1=bu.toString();
}
bu.setLength(0);
}
k--;
}
return s1;
}
public static void main(String args[])
{
String str="ccdaabcdbb";
String[] sstr={"ab","cd"};
String nstr=null;
samp t= new samp();
nstr=t.mini(str,sstr);
System.out.println("String is: "+nstr+"\n"+"Length is: "+nstr.length());
}
}
Here is my solution...
String str = "ccdaabcdbb";
while (str != null && (str.contains("cd") || str.contains("ab"))) {
if (str.contains("ab")) {
int index = str.indexOf("ab");
int length = str.length();
str = str.substring(0, index) + str.substring(index+2, length);
}
if (str.contains("cd")) {
int index = str.indexOf("cd");
int length = str.length();
str = str.substring(0, index) + str.substring(index+2, length);
}
}
System.out.println(str);
Here is my solution:
String str = "ccdaabcdbb";
while (str != null && (str.contains("cd") || str.contains("ab"))) {
if (str.contains("ab")) {
int index = str.indexOf("ab");
int length = str.length();
str = str.substring(0, index) + str.substring(index+2, length);
}
if (str.contains("cd")) {
int index = str.indexOf("cd");
int length = str.length();
str = str.substring(0, index) + str.substring(index+2, length);
}
}
System.out.println(str);
In Java
public static void main(String[] args) {
String S = "ccdaabcdbb";
List<String> subStrs = Arrays.asList("ab", "cd");
removeSubs(S, subStrs);
}
private static void removeSubs(String S, List<String> subStrs) {
int strLen = S.length();
int strLenChanged = strLen;
System.out.println(S);
for(String s : subStrs){
S = S.replace(s, "");
strLenChanged = S.length();
if(strLenChanged != strLen){
removeSubs(S, subStrs);
}
}
System.out.println("\nMinimum Length : "+S.length());
System.exit(1);
}
In Java
Put it in a class
public static void main(String[] args) {
String S = "ccdaabcdbb";
List<String> subStrs = Arrays.asList("ab", "cd");
removeSubs(S, subStrs);
}
private static void removeSubs(String S, List<String> subStrs) {
int strLen = S.length();
int strLenChanged = strLen;
System.out.println(S);
for(String s : subStrs){
S = S.replace(s, "");
strLenChanged = S.length();
if(strLenChanged != strLen){
removeSubs(S, subStrs);
}
}
System.out.println("\nMinimum Length : "+S.length());
System.exit(1);
}
import java.util.*;
public class StringSubstring {
public static void main(String[] args) {
// TODO Auto-generated method stub
int i, k=0, m=0,p;String messi;
String j[] = new String [5];
System.out.println("enter string");
Scanner s = new Scanner (System.in);
String bumblebee = s.nextLine();
System.out.println("enter no. of sub string");
int robben = s.nextInt();
for ( p = 0 ; p < robben; p++ )
{
System.out.println( " enter your substring here " ) ;
messi = s.nextLine();
j [p] = messi;
}
StringBuffer sb = new StringBuffer(bumblebee);
for (p= 0;p<robben; p++)
{
for(i=0; i<sb.length() ;i++ )
{
int van_persie = j[p].length();
if( sb.substring(i,van_persie).equals(j[p]) )
{
sb.delete(i,van_persie);
System.out.println(sb);
i=0;
}
else
continue;
}
}
}
}
char* miniMizeStr(string orig, vector<string> &list)
{
bool found = true;
while(found)
{
found = false;
for(int i=0; i<list.size(); i++)
{
size_t pos = orig.find(list[i]);
if(pos != string::npos)
{
orig.replace(pos, list[i].size(), "");
found = true;
}
}
}
return (char*)orig.c_str();
}
int main(int argc, const char * argv[])
{
string o = "ccdaabcdbb";
vector<string> list;
list.push_back("ab");
list.push_back("cd");
printf(">>> %s", miniMizeStr(o, list));
}
public static string RemoveSubstrings(this string source, IList<string> substringToRemove)
{
var intermediateVal = source;
substringToRemove.ToList().ForEach(a=>{
if (intermediateVal.Contains(a))
intermediateVal.Replace(a, string.Empty).RemoveSubstrings(substringToRemove);
});
return intermediateVal;
}
string targetString = "ccdaabcdbb";
string[] subString = new string[] { "ab", "cd" };
var algoRes = targetString.RemoveSubstrings(subString.ToList());
A simple solution in Java
public static void main(String[] args) {
String str="ccdaabcdbb ";
String[] sub={"ab","cd"};
System.out.println(solve(str,sub));
}
public static int solve(String str,String[] sub) {
boolean flag=true;
while(flag){
for (String i : sub) {
str=str.replaceAll(i,"");
}
flag=false;
for (String i : sub) {
flag=flag||str.contains(i);
if(flag) break; //will optimize. Can remove if need
}
}
return str.length()-1;
}
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
string s;
int n,i,j;
n=2;
s="ccccccababababddddddaaaaabbbbb";
string b[n];
b[0]="ab";
b[1]="cd";
string replay="";
for(j=0;j<n;j++)
{ while(s.find(b[j])!=string::npos)
{
for(i=0;i<n;i++)
{ while(s.find(b[i])!=string::npos)
{
s.replace(s.find(b[i]),2,replay);
cout<<s<<endl;
}
}
}}
cout<<s<<" "<<s.size();
getchar();
return 0;
}
Its not an optimized one but works perfectly
#include<iostream>
#include<string>
using namespace std;
void InsertionSort(string arr[],int n)
{
string s;
for(int i=1;i<n;i++)
{
int k=arr[i].size();
int j=i-1;
string s=arr[i];
while(j>=0 && k>(arr[j].size()))
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=s;
}
}
void SmallestString(string txt,string pat[],int x)
{
bool t=0;
for(int i=0;i<x;i++)
{
int siz=pat[i].size();
int txtsize=txt.size();
for(int j=0;j<=(txtsize-siz);j++)
{
int k=0,l=j;
while(k<siz && pat[i][k]==txt[l])
{
k++;
l++;
}
if(k==siz)
{
t=1;
int y=j;
while(l<txtsize)
{
txt[y]=txt[l];
txt[l]='\0';
l++;
y++;
}
if(y==j)
{
while(y<txtsize)
txt[y++]='\0';
}
txtsize=txt.size();
}
}
}
if(t==1)
{
SmallestString(txt,pat,x);
}
else
{
cout<<txt<<endl;
}
}
int main()
{
int x;
cin>>x;
string txt;
cin>>txt;
string pat[x];
int i=0;
while(i!=x)
{
cin>>pat[i];
i++;
}
InsertionSort(pat,x);
SmallestString(txt,pat,x);
}
I think the above code works properly. If there is any dispensry please comment
import java.util.HashSet;
import java.util.Stack;
public class removee_very_instance_of_those_n_substrings
{
public static void main(String []args)
{
removee_very_instance_of_those_n_substrings obj = new removee_very_instance_of_those_n_substrings ();
HashSet<String> set = new HashSet<String>();
set.add("ab");
set.add("cd");
System.out.println(obj.toRemoveSubstring("ccdacdbb",set));
}
private int toRemoveSubstring(String input,HashSet<String> set)
{
char input_array[] = input.toCharArray();
Stack<Character> stack = new Stack<Character>();
StringBuilder sub = new StringBuilder();
if(input.length()==0)
{
return 0;
}
else
{
for(int i=0;i<input.length();i++)
{
if(stack.isEmpty())
{
stack.push(input_array[i]);
continue;
}
else
{
sub.append(stack.peek()).append(input_array[i]);
System.out.println(sub);
if(set.contains(sub.toString()))
{
stack.pop();
}
else
{
stack.push(input_array[i]);
}
sub.setLength(0);
}
}
}
System.out.println(stack);
return stack.size();
}
}
Here is my implementation.. Is it bad ??
public class StringMatch {
public static void main(String[] args) {
String input = "ccdaabcdbb";
String[] substrings ={"ab","cd"};
String output = replaceWrapper(input,substrings);
System.out.println(output);
System.out.println(output.length());
}
private static String replaceWrapper(String input, String[] substrings) {
boolean isContains = false;
for (int i=0;i<substrings.length;i++){
if(input.contains(substrings[i])){
isContains = true;
break;
}
}
if(!isContains){
return input;
}
else{
for (int i=0;i<substrings.length;i++){
input = input.replace(substrings[i], "");
}
return replaceWrapper(input, substrings);
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int nomore=0;
String target="ccdaabcdbb";
Set s=new HashSet();
s.add("ab");
s.add("cd");
// Get an iterator
do
{
Iterator i = s.iterator();
// Display elements
while(i.hasNext())
{
String str=(i.next()).toString();
if(target.indexOf(str)!=-1) {
target=target.replaceAll(str,"");
}
else nomore=1;
}
}while(nomore==0);
System.out.println(target);
System.out.println("Minimum length of modified string is " + target.length());
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int nomore=0;
String target="ccdaabcdbb";
Set s=new HashSet();
s.add("ab");
s.add("cd");
// Get an iterator
do
{
Iterator i = s.iterator();
// Display elements
while(i.hasNext())
{
String str=(i.next()).toString();
if(target.indexOf(str)!=-1) {
target=target.replaceAll(str,"");
}
else nomore=1;
}
}while(nomore==0);
System.out.println(target);
System.out.println("Minimum length of modified string is " + target.length());
}
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
int main()
{
string str;
string substr, ss;
cout << "Enter String: "; cin >> str;
cout << "Enter Sub-strings(comma separated): "; cin >> substr;
bool iterateAgain = true;
while(iterateAgain)
{
iterateAgain = false;
istringstream iss(substr);
while(getline(iss, ss, ','))
{
while(1)
{
int pos = str.find(ss,0);
if(string::npos == pos) break;
str.erase(pos, ss.length());
iterateAgain = true;
}
}
}
cout << "Stripped string: " << str << endl;
cout << "Stripped string length: " << str.length() << endl;
return 0;
}
public class RemoveStrings {
private static String removeStrings(String str) {
if(str.contains("ab") || str.contains("cd")) {
str = str.replace("ab", "");
str = str.replace("cd", "");
return removeStrings(str);
}
return str;
}
public static void main(String args[]) {
String s = "ccdaabcdbb";
System.out.println(removeStrings(s));
}
}
Use Recursion !!
public class RemoveStrings {
private static String removeStrings(String str) {
if(str.contains("ab") || str.contains("cd")) {
str = str.replace("ab", "");
str = str.replace("cd", "");
return removeStrings(str);
}
return str;
}
public static void main(String args[]) {
String s = "ccdaabcdbb";
System.out.println(removeStrings(s));
}
}
public class StringSubString {
public static void main(String args[]){
System.out.println(getFinalStr("ccdaabcdbb ",new String[]{"ab","cd"}));
}
public static String getFinalStr(String word,String[] sub){
String returnWord=word;
for (int i = 0; returnWord.contains(sub[i]); i++) {
while (returnWord.contains(sub[i])){
returnWord = returnWord.replaceAll(sub[i], "");
i=0;
}
}
return returnWord;
}
}
public class StringSubString {
public static void main(String args[]){
System.out.println(getFinalStr("ccdaabcdbb ",new String[]{"ab","cd"}));
}
public static String getFinalStr(String word,String[] sub){
String returnWord=word;
for (int i = 0; returnWord.contains(sub[i]); i++) {
while (returnWord.contains(sub[i])){
returnWord = returnWord.replaceAll(sub[i], "");
i=0;
}
}
return returnWord;
}
}
static int minLength = Integer.MAX_VALUE;
static void findMinLenth(String input, List<String> remove,
Set<String> dp) {
if (dp.contains(input)) {
return;
}
dp.add(input);
boolean hasFound = false;
for (String one : remove) {
String newOne = input.replace(one, "");
hasFound |= !newOne.equals(newOne);
findMinLenth(newOne, remove, dp);
}
if (!hasFound && input.length() < minLength) {
minLength = input.length();
}
}
import java.lang.reflect.Array;
public class RemoveSubstring{
public static int subStringFree(String mainStr, String []subStrs) {
int i;
boolean flg = false;
String retStr = mainStr.substring(0);
int arrLen = Array.getLength(subStrs);
int flgCnt = 0;
while(flgCnt < (arrLen - 1)) {
for (i = 0; i < arrLen; i++) {
flg = true;
if (retStr.contains(subStrs[i].subSequence(0, subStrs[i].length()))){
int cnt = 0;
flgCnt --;
while (flg) {
int offsetIndx = retStr.indexOf(subStrs[i]);
if (offsetIndx > 0){
retStr = retStr.substring(cnt, offsetIndx) +
retStr.substring(offsetIndx + subStrs[i].length(), retStr.length());
}
else if (offsetIndx == 0){
retStr = retStr.substring(cnt + subStrs[i].length(), retStr.length());
}
else {
flg = false;
}
}
}
else {
flgCnt ++;
}
}
}
System.out.println(retStr);
return retStr.length();
}
public static void main(String []args){
String []subStrs = {"ab", "cd"};
String mainStr = "ccdaabcdbb";
System.out.println(subStringFree(mainStr, subStrs));
}
}
#include "stdafx.h"
#include <string.h>
#include <stdio.h>
int compressStr(char * data, char * substr[2], int count)
{
int rc = 0;
char * dest = NULL;
int active = 0;
char * tmp = data;
while (active != count)
{
int len = strlen(substr[active]);
tmp = data;
while (dest = strstr(tmp, substr[active]))
{
if (dest)
{
strcpy (dest, (dest+len));
rc = 1;
}
}
active ++;
}
return rc;
}
int _tmain(int argc, _TCHAR* argv[])
{
char data[] = {"ccdaabcdbb"};
char * substr[2] = { "ab", "cd" };
while (compressStr(data, substr, 2));
printf("len - %d\n", strlen(data));
return 0;
}
package com.utilities;
import java.util.HashMap;
import java.util.Map;
public class StringExample {
public static void main(String[] args) {
String str = "abababbbcdcdcd";
String[] strArr = new String[] {"ab","cd"};
Map<String, String> replaceStrMap = new HashMap<String, String>();
for (String str1:strArr) {
replaceStrMap.put(str1, str1);
}
int replaceCount = replaceStr(str, replaceStrMap);
System.out.println(replaceCount);
}
private static int replaceStr(String str, Map<String, String> replaceStrMap) {
int replaceCount = 0;
if (str == null || str.trim().length() == 0) {
return 0;
}
if (replaceStrMap == null || replaceStrMap.size() == 0) {
return 0;
}
char [] strArr = str.toCharArray();
StringBuffer replaceStr = new StringBuffer();
for (int i = 0;i<strArr.length-1;i++) {
replaceStr = new StringBuffer();
replaceStr = replaceStr.append(strArr[i]).append(strArr[i+1]);
if (replaceStrMap.containsKey(String.valueOf(replaceStr))) {
return replaceStr(str.substring(0,i) + str.substring(i+2, str.length()), replaceStrMap);
}
}
replaceCount = str.length();
return replaceCount;
}
}
package com.utilities;
import java.util.HashMap;
import java.util.Map;
public class StringExample {
public static void main(String[] args) {
String str = "abababbbcdcdcd";
String[] strArr = new String[] {"ab","cd"};
Map<String, String> replaceStrMap = new HashMap<String, String>();
for (String str1:strArr) {
replaceStrMap.put(str1, str1);
}
int replaceCount = replaceStr(str, replaceStrMap);
System.out.println(replaceCount);
}
private static int replaceStr(String str, Map<String, String> replaceStrMap) {
int replaceCount = 0;
if (str == null || str.trim().length() == 0) {
return 0;
}
if (replaceStrMap == null || replaceStrMap.size() == 0) {
return 0;
}
char [] strArr = str.toCharArray();
StringBuffer replaceStr = new StringBuffer();
for (int i = 0;i<strArr.length-1;i++) {
replaceStr = new StringBuffer();
replaceStr = replaceStr.append(strArr[i]).append(strArr[i+1]);
if (replaceStrMap.containsKey(String.valueOf(replaceStr))) {
return replaceStr(str.substring(0,i) + str.substring(i+2, str.length()), replaceStrMap);
}
}
replaceCount = str.length();
return replaceCount;
}
}
public void RemoveSubstringsFromGivenString(){
String[] substrings = {"ab", "cd"};
ArrayList<String> list = new ArrayList<>();
RemoveSubstrings("ccdaabcdbb", substrings, list);
//sort the list
Collections.sort(list);
System.out.println("output string:"+list.get(0));
System.out.println("min length: "+list.get(0).length());
}
private void RemoveSubstrings(String str, String[] substrings, ArrayList<String> list){
if((substrings.length == 0) || (str.length() == 0)){
list.add(str);
}
else if(str.length() > 0){
boolean containsSubstring = false;
for(String substring : substrings){
if(str.contains(substring)){
containsSubstring = true;
RemoveSubstrings(str.replaceAll(substring, ""), substrings, list);
}
}
if(!containsSubstring){
list.add(str);
}
}
}
public void RemoveSubstringsFromGivenString(){
String[] substrings = {"ab", "cd"};
ArrayList<String> list = new ArrayList<>();
RemoveSubstrings("ccdaabcdbb", substrings, list);
//sort the list
Collections.sort(list);
System.out.println("output string:"+list.get(0));
System.out.println("min length: "+list.get(0).length());
}
private void RemoveSubstrings(String str, String[] substrings, ArrayList<String> list){
if((substrings.length == 0) || (str.length() == 0)){
list.add(str);
}
else if(str.length() > 0){
boolean containsSubstring = false;
for(String substring : substrings){
if(str.contains(substring)){
containsSubstring = true;
RemoveSubstrings(str.replaceAll(substring, ""), substrings, list);
}
}
if(!containsSubstring){
list.add(str);
}
}
}
public class PlayWithStrings
{
public static void main (String ... args)
{
String input = "ccdaabcdbb";
String [] s = {"ab","cd"};
for (;;)
{
boolean found = false;
for ( int x=0 ; x <s.length ; x++)
{
if (input.indexOf(s[x]) != -1) {
input = input.replaceAll (s[x],"");
found = true;
}
}
if (!found) break;
}
System.out.println(input);
}
}
public class PlayWithStrings
{
public static void main (String ... args)
{
String input = "ccdaabcdbb";
String [] s = {"ab","cd"};
for (;;)
{
boolean found = false;
for ( int x=0 ; x <s.length ; x++)
{
if (input.indexOf(s[x]) != -1) {
input = input.replaceAll (s[x],"");
found = true;
}
}
if (!found) break;
}
System.out.println(input);
}
}
I don't understand, is it supposed to be a hard question?
public string Removesub(string input, params string[] sub) {
string curr = input;
bool stop = false;
while (!stop) {
bool replaced = false;
foreach (string s in sub) {
int idx = curr.IndexOf(s);
if (idx >= 0)
{
curr = curr.Replace(s, "");
replaced = true;
}
}
stop = !replaced;
}
return curr;
}
public string Removesub(string input, params string[] sub) {
string curr = input;
bool stop = false;
while (!stop) {
bool replaced = false;
foreach (string s in sub) {
int idx = curr.IndexOf(s);
if (idx >= 0)
{
curr = curr.Replace(s, "");
replaced = true;
}
}
stop = !replaced;
}
return curr;
}
Using Java you can use regular expressions.
private int replaceStrings(String a, Set<String> strings) {
if (a == null) {
throw new IllegalArgumentException("One of the arguments was null");
} else if (strings == null) {
return a;
}
String newString = a;
String oldString = null;
StringBuilder builder = new StringBuilder();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()) {
builder.append(iterator.next()).append("|");
}
builder.deleteCharAt(builder.length() - 1);
while (!newString.equals(oldString)) {
oldString = newString;
newString = newString.replaceAll(builder.toString(), "");
}
return newString.length();
}
HackerRank allows use of multiple languages. I wrote the implementation in perl.
use strict;
use Getopt::Long;
my %opt;
GetOptions(\%opt,"mainstring=s","substrings=s");
my $mainstring = $opt{mainstring};
my @substrings = split (" ",$opt{substrings});
my $flag = 1;
while ($flag == 1) {
foreach my $subs (@substrings) {
if ($mainstring =~ m/${subs}/) {
$mainstring =~ s/${subs}//g;
print "Main string is : $mainstring \n";
$flag = 1;
} else {
$flag = 0;
}
}
}
print "Shorted string is $mainstring with length " . length($mainstring);
call to the script should be like
remove_substrings.pl -mainstring "ccdaabcddb" -substrings "ab cd"
public static int GetMinLength(string initialString, List<string> substringList)
{
int minLength = initialString.Length;
foreach (string substring in substringList)
{
if (initialString.Contains(substring))
{
string newString = initialString.Replace(substring, string.Empty);
minLength = GetMinLength(newString, substringList);
}
}
return minLength;
}
Simplest of all
public class StringDemo {
public static void main(String[] args) {
String substr1 = "ab";
String substr2 = "cd";
String str = "ccdaabcdbb";
while(str.indexOf(substr1) != -1 || str.indexOf(substr2) != -1 ){
str = str.replaceAll(substr1, "");
str = str.replaceAll(substr2, "");
}
System.out.println(str);
}
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LENGTH 20
#define PATTERN (*strptr == 'a' && *strptr1 == 'b' || *strptr == 'c' && *strptr1 == 'd')
int main(void)
{
char str[LENGTH];
char *strptr = str, *strptr1 = strptr+1, *strptr2 = NULL;
/* pattern of substring to match in a string, S is either 'ab' or 'cd' */
/* this solution isn't perfect in that it can handle only checking of
/* two character substrings. Any more would need slight tweaking of the code */
printf("Original string is: \n");
scanf("%s",str);
while (*strptr1 != '\0') {
if PATTERN {
strptr2 = strptr1 + 1;
strcpy(strptr,strptr2);
strptr = str;
} // end if loop
else
strptr = strptr1;
strptr1 = strptr+1;
strptr2 = NULL;
} // end while loop
printf("Modified string is: %s\n",str);
printf("Modified string length is: %d\n",strlen(str));
system("pause");
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LENGTH 20
#define PATTERN (*strptr == 'a' && *strptr1 == 'b' || *strptr == 'c' && *strptr1 == 'd')
int main(void)
{
char str[LENGTH];
char *strptr = str, *strptr1 = strptr+1, *strptr2 = NULL;
/* pattern of substring to match in a string, S is either 'ab' or 'cd' */
/* this solution isn't perfect in that it can handle only checking of
/* two character substrings. Any more would need slight tweaking of the code */
printf("Original string is: \n");
scanf("%s",str);
while (*strptr1 != '\0') {
if PATTERN {
strptr2 = strptr1 + 1;
strcpy(strptr,strptr2);
strptr = str;
} // end if loop
else
strptr = strptr1;
strptr1 = strptr+1;
strptr2 = NULL;
} // end while loop
printf("Modified string is: %s\n",str);
printf("Modified string length is: %d\n",strlen(str));
system("pause");
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LENGTH 20
#define PATTERN (*strptr == 'a' && *strptr1 == 'b' || *strptr == 'c' && *strptr1 == 'd')
int main(void)
{
char str[LENGTH];
char *strptr = str, *strptr1 = strptr+1, *strptr2 = NULL;
/* pattern of substring to match in a string, S is either 'ab' or 'cd' */
/* this solution isn't perfect in that it can handle only checking of
/* two character substrings. Any more would need slight tweaking of the code */
printf("Original string is: \n");
scanf("%s",str);
while (*strptr1 != '\0') {
if PATTERN {
strptr2 = strptr1 + 1;
strcpy(strptr,strptr2);
strptr = str;
} // end if loop
else
strptr = strptr1;
strptr1 = strptr+1;
strptr2 = NULL;
} // end while loop
printf("Modified string is: %s\n",str);
printf("Modified string length is: %d\n",strlen(str));
system("pause");
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LENGTH 20
#define PATTERN (*strptr == 'a' && *strptr1 == 'b' || *strptr == 'c' && *strptr1 == 'd')
int main(void)
{
char str[LENGTH];
char *strptr = str, *strptr1 = strptr+1, *strptr2 = NULL;
/* pattern of substring to match in a string, S is either 'ab' or 'cd' */
/* this solution isn't perfect in that it can handle only checking of
/* two character substrings. Any more would need slight tweaking of the code */
printf("Original string is: \n");
scanf("%s",str);
while (*strptr1 != '\0') {
if PATTERN {
strptr2 = strptr1 + 1;
strcpy(strptr,strptr2);
strptr = str;
} // end if loop
else
strptr = strptr1;
strptr1 = strptr+1;
strptr2 = NULL;
} // end while loop
printf("Modified string is: %s\n",str);
printf("Modified string length is: %d\n",strlen(str));
system("pause");
}
public static void main(String[] args) {
//remove n substrings from string
String str1 = "tutorials point is good website";
String[] subStr = {"tor", "ls", "fine", " g"};
for (int i = 0; i < subStr.length; i++) {
if (str1.contains(subStr[i])) {
str1 = str1.replace(subStr[i], "");
}
}
//ans may be "tuia point isood website"
System.out.println("Ans " + str1);
}
package com.hackerearth.gs.practice;
import java.util.Scanner;
public class SubStringRemover {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String subStrs[] = sc.nextLine().split(" ");
sc.close();
System.out.println(removeSubtrings(0, str, subStrs).length());
}
private static String removeSubtrings(int idx,String str, String[] subStrs) {
if(idx < subStrs.length && str.contains(subStrs[idx]))
{
str = str.replaceAll(subStrs[idx], "");
str = removeSubtrings(0,str, subStrs);
}
else if (idx < subStrs.length -1 )
{
str = removeSubtrings(idx+1,str, subStrs);
}
return str;
}
}
package com.hackerearth.gs.practice;
import java.util.Scanner;
public class SubStringRemover {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String subStrs[] = sc.nextLine().split(" ");
sc.close();
System.out.println(removeSubtrings(0, str, subStrs).length());
}
private static String removeSubtrings(int idx,String str, String[] subStrs) {
if(idx < subStrs.length && str.contains(subStrs[idx]))
{
str = str.replaceAll(subStrs[idx], "");
str = removeSubtrings(0,str, subStrs);
}
else if (idx < subStrs.length -1 )
{
str = removeSubtrings(idx+1,str, subStrs);
}
return str;
}
}
String s = "ccdaabcdbb";
String[] substring = {"ab", "cd"};
String sub = s;
for(int i = 0 ; i <= s.length(); i ++){
sub = s.substring(0, i).replaceAll(substring[0], "").replaceAll(substring[1], "");
}
sub = sub.replaceAll(substring[0], "").replaceAll(substring[1], "");
System.out.println(sub + " " + "length:" + sub.length());
String s = "ccdaabcdbb";
String[] substring = {"ab", "cd"};
String sub = s;
for(int i = 0 ; i <= s.length(); i ++){
sub = s.substring(0, i).replaceAll(substring[0], "").replaceAll(substring[1], "");
}
sub = sub.replaceAll(substring[0], "").replaceAll(substring[1], "");
System.out.println(sub + " " + "length:" + sub.length());
and
def min_substr(S, arr, index_first = None):
match_count = map(lambda x : x in S, arr).count(True)
best_match = len(S)
best_index = None
mystring = S
myarray = arr
while match_count > 0:
if index_first is not None:
mystring = mystring.replace(myarray[index_first], '', 1)
index_first = None
else:
for j in [k for k in range(len(myarray)) if myarray[k] in mystring]:
current_match = min_substr(mystring, myarray, index_first = j)
if current_match < best_match:
best_match = current_match
best_index = j
mystring = mystring.replace(myarray[j], '', 1)
best_match = len(mystring)
match_count = map(lambda x : x in mystring, myarray).count(True)
return best_match
and
tested with :
arr1 = ['ab', 'bcd']
S1 = 'abcd'
print min_substr(S1, arr1)
S2 = 'ccdaabcdbb'
arr2 = ['ab', 'cd']
print min_substr(S2, arr2)
another possible solution in Go
package main
import (
"fmt"
"strings"
)
func main() {
output := "ccdaabcdbb"
var n = [2]string{"ab", "cd"}
thres := 0
if len(n[0]) >= len(n[1]) {
thres = len(n[0])
} else {
thres = len(n[1])
}
for {
found := false
if strings.Index(output, n[0]) != -1 {
output = strings.Replace(output, n[0], "", 1)
}
if strings.Index(output, n[1]) != -1 {
found = true
output = strings.Replace(output, n[1], "", 1)
}
if len(output) <= thres {
break
}
if !found {
break
}
}
fmt.Println(output, len(output))
}
public class Problem1 {
public String reduce(String actual,String sub1,String sub2){
int previouslength = 0;
while(previouslength != actual.length()){
previouslength = actual.length();
actual = actual.replace(sub1, "");
actual = actual.replace(sub2, "");
}
return actual;
}
public static void main(String[] args){
Problem1 pb1 = new Problem1();
String result = pb1.reduce("ccdaabcdbb", "ab", "cd");
System.out.println("Result : "+result);
}
}
public class Problem1 {
public String reduce(String actual,String sub1,String sub2){
int previouslength = 0;
while(previouslength != actual.length()){
previouslength = actual.length();
actual = actual.replace(sub1, "");
actual = actual.replace(sub2, "");
}
return actual;
}
public static void main(String[] args){
Problem1 pb1 = new Problem1();
String result = pb1.reduce("ccdaabcdbb", "ab", "cd");
System.out.println("Result : "+result);
}
}
static String getSubstring(String string,ArrayList<String> substringList)
{
if(string.isEmpty() || string == null)
return null;
for(int i=0; i < substringList.size(); i++)
{
if(string.contains(substringList.get(i)))
{
string = string.replace(substringList.get(i),"");
System.out.println(string);
i=0;
}
}
return string;
}
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char s[100],ch[100];
cin>>s;
int n;
cin>>n;
char c[n][100];
int a[n];
for(int i=0;i<n;i++)
{
cin>>c[i];
a[i]=strlen(c[i]);
}
int l=strlen(s),k,f,y=0;
for(int i=0;i<l;i++)
{
for(int j=0;j<n;j++)
{
if(c[j][0]==s[i])
{
k=i;
i++;
f=0;
for(int x=1;x<a[j];x++,i++)
{
if(s[i]!=c[j][x])
{
f=1;
break;
}
}
if(f)
{
i=k;
}
}
}
ch[y++]=s[i];
}
ch[y]='\0';
cout<<ch<<endl;
}
//I hope this works
String ss_main = "ccdaabcdbb";
ArrayList<String> ss_temp = new ArrayList<String>();
ss_temp.add("ab");
ss_temp.add("cd");
while (ss_main.length() > 0) {
int flag = 0;
for (int i = 0; i < ss_temp.size(); i++) {
if (ss_main.contains(ss_temp.get(i))) {
System.out.println(ss_main+ " " + ss_temp.get(i));
ss_main = ss_main.replace(ss_temp.get(i), "");
flag = 1;
}
}
if (flag == 0) {
break;
}
}
System.out.println(ss_main);
}
private String getMinCountOfSubstring(String input, List<String> subStrings) {
for (Iterator<String> it = subStrings.iterator(); it.hasNext();) {
String subString = it.next();
if (input.contains(subString)) {
input = input.replace(subString, "");
return getMinCountOfSubstring(input, subStrings);
}
}
return input;
}
private String getMinCountOfSubstring(String input, List<String> subStrings) {
for (Iterator<String> it = subStrings.iterator(); it.hasNext();) {
String subString = it.next();
if (input.contains(subString)) {
input = input.replace(subString, "");
return getMinCountOfSubstring(input, subStrings);
}
}
return input;
}
public class MaxLength {
public static int getLength(String in,String r1,String r2){
while(in.contains(r1)){
in=in.replace(r1,"");
while(in.contains(r2))
in=in.replace(r2,"");
}
System.out.println("Final String is :"+in);
return in.length();
}
public static void main(String[] args) {
int len=getLength("ccdaabcdbb","ab","cd");
System.out.println("min length is :"+len);
System.out.println("------------------------------");
int len2=getLength("abc","ab","cd");
System.out.println("min length is :"+len2);
System.out.println("------------------------------");
int len3=getLength("abcd","ab","cd");
System.out.println("min length is :"+len3);
}
}
public class Main {
public static void main(String[] args) {
String fullString = "ccdaabcdbdb";
String removableSubString1 = "ab";
String removableSubString2 = "cd";
while(fullString.contains(removableSubString2) || fullString.contains(removableSubString1)){
fullString = removeSubString(fullString, removableSubString1, removableSubString2);
}
System.out.println(fullString);
}
private static String removeSubString( String fullString, String removableSubString1, String removableSubString2){
for (int i = 0; i < fullString.length()-1 ; i++){
String temp1 = fullString.charAt(i) +""+ fullString.charAt(i+1);
if(temp1.equalsIgnoreCase(removableSubString1) ||
temp1.equalsIgnoreCase(removableSubString2)){
fullString = fullString.replace(temp1,"");
}
}
return fullString;
}
}
public class Main{
public static void main(String[] args){
String fullString = "ccdaabcdbdb";
String removableSubString1 = "ab";
String removableSubString2 = "cd";
while(fullString.contains(removableSubString2) || fullString.contains(removableSubString1)){
fullString = removeSubString(fullString, removableSubString1, removableSubString2);
}
System.out.println(fullString);
}
private static String removeSubString( String fullString, String removableSubString1, String removableSubString2){
for (int i = 0; i < fullString.length()-1 ; i++){
String temp1 = fullString.charAt(i) +""+ fullString.charAt(i+1);
if(temp1.equalsIgnoreCase(removableSubString1) ||
temp1.equalsIgnoreCase(removableSubString2)){
fullString = fullString.replace(temp1,"");
}
}
return fullString;
}
}
public class Main {
public static void main(String[] args) {
String fullString = "ccdaabcdbdb";
String removableSubString1 = "ab";
String removableSubString2 = "cd";
while(fullString.contains(removableSubString2) || fullString.contains(removableSubString1)){
fullString = removeSubString(fullString, removableSubString1, removableSubString2);
}
System.out.println(fullString);
}
private static String removeSubString( String fullString, String removableSubString1, String removableSubString2){
for (int i = 0; i < fullString.length()-1 ; i++){
String temp1 = fullString.charAt(i) +""+ fullString.charAt(i+1);
if(temp1.equalsIgnoreCase(removableSubString1) ||
temp1.equalsIgnoreCase(removableSubString2)){
fullString = fullString.replace(temp1,"");
}
}
return fullString;
}
}
class RemoveString
{
public static void main (String[] args) {
StringBuffer word = new StringBuffer("ccdaabcdbb");
while(word.indexOf("ab")>=0 || word.indexOf("cd")>=0)
{
if (word.indexOf("ab")>=0)
word.delete(word.indexOf("ab"),word.indexOf("ab")+2);
if (word.indexOf("cd")>=0)
word.delete(word.indexOf("cd"),word.indexOf("cd")+2);
}
System.out.println(word);
}
}
{class RemoveString
{
public static void main (String[] args) {
StringBuffer word = new StringBuffer("ccdaabcdbb");
while(word.indexOf("ab")>=0 || word.indexOf("cd")>=0)
{
if (word.indexOf("ab")>=0)
word.delete(word.indexOf("ab"),word.indexOf("ab")+2);
if (word.indexOf("cd")>=0)
word.delete(word.indexOf("cd"),word.indexOf("cd")+2);
}
System.out.println(word);
}
}}
class RemoveString
{
public static void main (String[] args) {
StringBuffer word = new StringBuffer("ccdaabcdbb");
while(word.indexOf("ab")>=0 || word.indexOf("cd")>=0)
{
if (word.indexOf("ab")>=0)
word.delete(word.indexOf("ab"),word.indexOf("ab")+2);
if (word.indexOf("cd")>=0)
word.delete(word.indexOf("cd"),word.indexOf("cd")+2);
}
System.out.println(word);
}
}
{{class RemoveString
{
public static void main (String[] args) {
StringBuffer word = new StringBuffer("ccdaabcdbb");
while(word.indexOf("ab")>=0 || word.indexOf("cd")>=0)
{
if (word.indexOf("ab")>=0)
word.delete(word.indexOf("ab"),word.indexOf("ab")+2);
if (word.indexOf("cd")>=0)
word.delete(word.indexOf("cd"),word.indexOf("cd")+2);
}
System.out.println(word);
}
}}}
class RemoveString
{
public static void main (String[] args) {
StringBuffer word = new StringBuffer("ccdaabcdbb");
while(word.indexOf("ab")>=0 || word.indexOf("cd")>=0)
{
if (word.indexOf("ab")>=0)
word.delete(word.indexOf("ab"),word.indexOf("ab")+2);
if (word.indexOf("cd")>=0)
word.delete(word.indexOf("cd"),word.indexOf("cd")+2);
}
System.out.println(word);
}
}
{class RemoveString
{
public static void main (String[] args) {
StringBuffer word = new StringBuffer("ccdaabcdbb");
while(word.indexOf("ab")>=0 || word.indexOf("cd")>=0)
{
if (word.indexOf("ab")>=0)
word.delete(word.indexOf("ab"),word.indexOf("ab")+2);
if (word.indexOf("cd")>=0)
word.delete(word.indexOf("cd"),word.indexOf("cd")+2);
}
System.out.println(word);
}
}}
{class RemoveString
{
public static void main (String[] args) {
StringBuffer word = new StringBuffer("ccdaabcdbb");
while(word.indexOf("ab")>=0 || word.indexOf("cd")>=0)
{
if (word.indexOf("ab")>=0)
word.delete(word.indexOf("ab"),word.indexOf("ab")+2);
if (word.indexOf("cd")>=0)
word.delete(word.indexOf("cd"),word.indexOf("cd")+2);
}
System.out.println(word);
}
}}
StringBuffer word = new StringBuffer("ccdaabcdbb");
while(word.indexOf("ab")>=0 || word.indexOf("cd")>=0)
{
if (word.indexOf("ab")>=0)
word.delete(word.indexOf("ab"),word.indexOf("ab")+2);
if (word.indexOf("cd")>=0)
word.delete(word.indexOf("cd"),word.indexOf("cd")+2);
}
System.out.println(word);
{StringBuffer word = new StringBuffer("ccdaabcdbb");
while(word.indexOf("ab")>=0 || word.indexOf("cd")>=0)
{
if (word.indexOf("ab")>=0)
word.delete(word.indexOf("ab"),word.indexOf("ab")+2);
if (word.indexOf("cd")>=0)
word.delete(word.indexOf("cd"),word.indexOf("cd")+2);
}
System.out.println(word);}
StringBuffer word = new StringBuffer("ccdaabcdbb");
while(word.indexOf("ab")>=0 || word.indexOf("cd")>=0)
{
if (word.indexOf("ab")>=0)
word.delete(word.indexOf("ab"),word.indexOf("ab")+2);
if (word.indexOf("cd")>=0)
word.delete(word.indexOf("cd"),word.indexOf("cd")+2);
}
System.out.println(word);
In most (if not all) above answers I don't see the order of deletions is being considered. Suppose the string is 'abbc' and the substrings are 'a','b','abc'. With good deletion order the result is '', but I think all answers cannot get that. I don't have a solution yet, but I'd like people to think about this (and the similar) case.
the use of indexOf, just hides the complexity of searching the string.
The idea is go through the string from index 0 to n
For each index i check if string x..i is deletable (one of the substrings we got) x < i
this is done in O(1) via hash table for each index i
for each such of these substrings the size we can reach is dp[x-1] or 0
for i we remember the minimum and store it in dp[i]
Solution: o(n^2)
space : o(n)
public class EliminateSubs {
public static String removeSubstring(String str){
for(int n=0; n<=str.length(); n++) {
if (null != str && !str.equals("")) {
if (str.contains("ab")) {
str = str.replace("ab", "");
}
if (str.contains("cd")) {
str = str.replace("cd", "");
}
}
}
return str;
}
public static void main(String[] args) {
System.out.println("" + removeSubstring("ccdaabcdbabcdcdcdcghghgb"));
}
}
public class EliminateSubs {
public static String removeSubstring(String str){
for(int n=0; n<=str.length(); n++) {
if (null != str && !str.equals("")) {
if (str.contains("ab")) {
str = str.replace("ab", "");
}
if (str.contains("cd")) {
str = str.replace("cd", "");
}
}
}
return str;
}
public static void main(String[] args) {
System.out.println("" + removeSubstring("ccdaabcdbabcdcdcdcghghgb"));
}
}
public class EliminateSubs {
public static String removeSubstring(String str){
for(int n=0; n<=str.length(); n++) {
if (null != str && !str.equals("")) {
if (str.contains("ab")) {
str = str.replace("ab", "");
}
if (str.contains("cd")) {
str = str.replace("cd", "");
}
}
}
return str;
}
public static void main(String[] args) {
System.out.println("" + removeSubstring("ccdaabcdbabcdcdcdcghghgb"));
}
}
use KnuthMorrisPrat algo to find index of occurences of substring. and then replace the substring with null.
here is working code for KMP algo.
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void computeLPSArray(char *pat, int M, int *lps);
void KMPSearch(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
// create lps[] that will hold the longest prefix suffix values for pattern
int *lps = (int *)malloc(sizeof(int)*M);
int j = 0; // index for pat[]
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
while(i < N)
{
if(pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
printf("Found pattern at index %d \n", i-j);
j = lps[j-1];
}
// mismatch after j matches
else if(pat[j] != txt[i])
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if(j != 0)
j = lps[j-1];
else
i = i+1;
}
}
free(lps); // to avoid memory leak
}
void computeLPSArray(char *pat, int M, int *lps)
{
int len = 0; // lenght of the previous longest prefix suffix
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i] for i = 1 to M-1
while(i < M)
{
if(pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if( len != 0 )
{
// This is tricky. Consider the example AAACAAAA and i = 7.
len = lps[len-1];
// Also, note that we do not increment i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// Driver program to test above function
int main()
{
char *txt = "ABABDABACDABABCABAB";
char *pat = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
import java.util.Scanner;
public class SubStringMinLength {
// main method starts
public static void main (String...strings) {
// get the scanner object
Scanner scanner = new Scanner(System.in);
SubStringMinLength subStringMinLength = new SubStringMinLength();
String str = scanner.next(); // input string
int number = scanner.nextInt();
String[] subStrings = new String[number];
for (int i = 0; i < number; i++) {
subStrings[i] = scanner.next();
}
int i = 0;
while (i < number) {
String subString = subStrings[i];
str = subStringMinLength.findSubString (str, subString.length(), subString);
i++;
for (int j = 0; j < i; j++) {
if (str.contains(subStrings[j])) {
i = j;
break;
}
}
}
System.out.println(str.length());
scanner.close(); // close the resources
}
// main method ends here
/**
* SubString the initial String
*
* @param str
* @param initialPos
* @param finalPos
* @param subString
*
* @return
*/
private String findSubString (String str, int finalPos, String subString) {
// iterate to the length of the String
for (int i = 0; i < str.length() - finalPos + 1; i++) {
String temp = str.substring(i, finalPos + i);
if (temp.equals(subString)) {
str = str.substring(0, i) + str.substring(finalPos + i, str.length());
str = findSubString(str, finalPos, subString);
}
}
return str;
}
}
Here is a possible solution in Java:
- Ognian June 09, 2014