how to get smallest string from big string (concat from small string)

user_5711656 0
Viewed 1109

how to find the smallest string from a string . in other words find the smallest string such that it can be concatenated some number of times to obtain big string.

Input rbrb output rb (my function is working fine)

Another example

Input bcdbcdbcdbcd output :bcd (my function working fine)

I tried like this.

function getSmallestString(s){
  
  let i= 0;
  let tem = '';
 
  
  while(true){
     let mid = s.length/2;
    let tem = s.substring(0,mid);
    if(tem + tem == s){
      s= tem
    }else {
      return s;
    }
    
  }
  
}

console.log('bcdbcdbcdbcd')

https://jsbin.com/liracurala/1/edit?html,js,output

here my case fail

function getSmallestString(s){
  
  let i= 0;
  let tem = '';
 
  
  while(true){
     let mid = Math.floor(s.length/2);
    let tem = s.substring(0,mid);
    if(tem + tem == s){
      s= tem
    }else {
      return s;
    }
    
  }
  
}

console.log(getSmallestString('ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo'))

Expected output is o

Each answer fail in this case lrbb expected output lrbb

javascript
4 Answers
function getSmallestString(str) {
    var current = "";
    for(var i = 0, len = str.length; i < len; ++i) {
        current += str[i];
        if(str.replace(new RegExp(current,"g"),"") == "") return current
    }
}
user_44154090

If I understood your question correctly, your task was to find the smallest sequence of characters from a string that could be duplicated to replicate the original string.

wordIsDivisibleBy does that job.

function wordIsDivisibleBy(word) {
    
    for (let distance = 1; distance <= (word.length / 2) ; distance++) { 
      if (Number.isInteger(word.length / distance)) {
        let sequence = word.slice(0, distance);
        let numToRepeat = word.length / distance;
        if (sequence.repeat(numToRepeat) === word) {
            console.log(sequence);
            return;
        }
      }
    }
    console.log(word)
}
  
wordIsDivisibleBy("a");
wordIsDivisibleBy("aa");
wordIsDivisibleBy("ab");
wordIsDivisibleBy("aaa");
wordIsDivisibleBy("aab");
wordIsDivisibleBy("abbabbabb");
wordIsDivisibleBy("abbabbabx");

How it works

This function takes a chunk of the word (always starting from the beginning of the word). We call this chunk sequence. The function asks if every same-sized adjacent chunk is the same as sequence. sequence's length starts off at 1 character and increases at each iteration of the main for loop - but not before sequence would reach over half the size of the original word. The first sequence that passes the test is our answer. If no sequence passes the test, the original word is logged out.

user_140372830

Let m be the size of the smaller substring. To improve the time complexity you can use the fact that the substring size possible would be of the size of the divisors of m. So, the time complexity becomes O(N*sqrt(N)). Here is the code for it -

#include<bits/stdc++.h>
using namespace std;

#define int long long int

int findSmallestDivisor(string s, string t){
    int n = s.size();
    int m = t.size();
    if(n%m != 0)
        return -1;
    string temp="";
    int val = n/m;
    for(int i=0;i<val;i++)
        temp += t;
    if(temp != s)
        return -1;
    vector<int> V;
    for(int i=1;i<=sqrt(m);i++){
        if(m%i == 0){
            V.push_back(i);
            if(i != m/i)
                V.push_back(m/i);
        }
    }
    int res = -1;
    sort(V.begin(), V.end());
    for(auto x: V){
        string temp = "";
        string temp1 = t.substr(0,x);
        val = m/x;
        for(int j=0;j<val;j++)
            temp += temp1;
        if(temp == t){
            res = x;
            break;
        }
    }

    return res;
}

int32_t main(){
    string S, T;
    cin>>S>>T;
    cout<<findSmallestDivisor(S,T);

    return 0;
}

For improving time complexity you can think of a solution in a different way. The possible substring length will be the LCM of the difference of consecutive position for each character. For example -

t = "bcdbcd"
position of 'b' - 0, 3 - Lcm of difference of consecutive position is 3
position of 'c' - 1, 4 - Lcm of difference of consecutive position is 3
position of 'd' - 2, 5 - Lcm of difference of consecutive position is 3
So, LCM of all the position difference is also 3 in this case.

This makes the program run very fast. In the worst case the code will run in O(k*N) where k will be some small constant factor. A rigorous TC analysis is required. I just tried to make the code as faster as I could. Here is my code -

#include<bits/stdc++.h>
using namespace std;

#define int long long int

int findSmallestDivisor(string s, string t){
    int n = s.size();
    int m = t.size();
    if(n%m != 0)
        return -1;
    string temp="";
    int val = n/m;
    for(int i=0;i<val;i++)
        temp += t;
    if(temp != s)
        return -1;
    int res = -1;
    vector<int> V[26];
    for(int i=0;i<m;i++)
        V[t[i]-'a'].push_back(i);
    for(int i=0;i<26;i++){
        if(V[i].size() == 1)
            res = m;
    }
    if(res != -1)
        return m;
    int index;
    for(int i=0;i<26;i++){
        if(V[i].size() >= 2)
            index = i;
    }
    val = V[index][1]-V[index][0];
    for(int i=0;i<26;i++){
        for(int j=1;j<V[i].size();j++){
            int temp1 = V[i][j]-V[i][j-1];
            int gcd = __gcd(val, temp1);
            val = (temp1*val)/gcd;
            if(val > m)
                break;
        }
        if(val > m)
            break;
    }
    if(val > m)
        return m;
    int x = val;
    while(x <= m){
        temp = "";
        string temp1 = t.substr(0,x);
        val = m/x;
        for(int j=0;j<val;j++)
            temp += temp1;
        if(temp == t){
            res = x;
            break;
        }
        x += val;
    }

    return res;
}

int32_t main(){
    string S, T;
    cin>>S>>T;
    cout<<findSmallestDivisor(S,T);

    return 0;
}
user_145494860

Check gradually

I hope I have found the right solution for you :)

I use str.repeat() to create a repeat to check with the string.

function findSmallestStringRepeat(string) {
  let myMatchStr = string;
  for (let i = 0; i < string.length - 1; i++) {
    myMatchStr = string.substr(0, i + 1);
    const compareString = myMatchStr.repeat(Math.ceil(string.length / myMatchStr.length));
    if (string === compareString.substr(0, string.length)) return myMatchStr;
  }
  return string; // There are no repeats in string to get smaller string
}

And add snippet with checks:

function findSmallestStringRepeat(string) {
  let myMatchStr = string;
  for (let i = 0; i < string.length - 1; i++) {
    myMatchStr = string.substr(0, i + 1);
    const compareString = myMatchStr.repeat(Math.ceil(string.length / myMatchStr.length));
    if (string === compareString.substr(0, string.length)) return myMatchStr;
  }
  return string; // There are no repeats in string to get smaller string
}

const string1 = "lrbb";
const string2 = "bb";
const string3 = "abab";
const string4 = "abaca";
const string5 = "abcdefghi";
const string6 = "abcabcabc";
const string7 = "aabbbaaa";

console.log('For String:', string1 ,' - We get:', findSmallestStringRepeat(string1));
console.log('For String:', string2 ,' - We get:', findSmallestStringRepeat(string2));
console.log('For String:', string3 ,' - We get:', findSmallestStringRepeat(string3));
console.log('For String:', string4 ,' - We get:', findSmallestStringRepeat(string4));
console.log('For String:', string5 ,' - We get:', findSmallestStringRepeat(string5));
console.log('For String:', string6 ,' - We get:', findSmallestStringRepeat(string6));
console.log('For String:', string7 ,' - We get:', findSmallestStringRepeat(string7));

user_108699290
Related