CODEWITHSUNDEEP
stringalgorithmsubstring
emufan4568
emufan4568

Reputation: 55

Algorithm: Optimally splitting a string into 3 substrings

For a while now I have been trying to wrap my head around this seemingly very simple problem. Given a string k, we have to find the optimal way to split that string k into exactly 3 substrings k1, k2, k3 such as that k1 + k2 + k3 = k. A split is optimal if and only if by reversing each substring and joining them back together we get the lexicographically smallest result possible.

For example take a string k = "anakonda". The optimal way to split it is k1 = "a", k2 = "na", k3 = "konda" because after reversing (k1 = "a", k2 = "an", k3 = "adnok") we get k1 + k2 + k3 = "aanadnok" which is the lexicographically smallest possible result.

My first approach was to always end a substring at the next lexicographically smallest character.

std::string str = "anakonda"

int first = find_min(str, 0, str.size() - 3); // Need to have at least 3 substrings so cannot search to the end
std::reverse(str.begin(), str.begin() + first + 1);

...

However this approach is flawed as given the string k = "ggggffffa" the algorithm would not work. I am clueless as to how to correctly solve this problem. So, I am asking for a theoretical solution so that I can try to implement it myself.

Upvotes: 4

Views: 846

Answers (1)

Aleksey Kuchkin
Aleksey Kuchkin

Reputation: 143

This algorithm solves the problem but may require optimization:

#include <iostream>
#include <string>

std::string foo(std::string* ss) 
{ 
    std::string res;
    for (int i = 0; i < 3; i++)
        for (int j = ss[i].size()-1; j >= 0; j--) 
        res.push_back(ss[i][j]);
    return res;
}

int main()
{
  std::string s = "ggggffffa";
  std::string res = "";
  for (unsigned int i = 1; i < s.size() - 1; i++)
    for (unsigned int j = 0; j < i; j++)
    {
        std::string ss[3] = {s.substr(0, j+1), s.substr(j+1, i-j), s.substr(i+1)};
        std::string r = foo(ss);
        if (r < res || res == "") res = r;
    }
    std::cout << res << std::endl;  
}

Description:

  1. We go through two iterators (the first iterator from the first element to the end of the string, the second iterator from the zero element to the first iterator) in this way we determine all possible indexes for splitting the string.
for (unsigned int i = 1; i < s.size() - 1; i++)
    for (unsigned int j = 0; j < i; j++)
  1. Split string at indices i, j and write three substrings in the array of strings;
std::string ss[3] = {s.substr(0, j+1), s.substr(j+1, i-j), s.substr(i+1)};
  1. Сall the function foo which reverse each substring, concatenate the three parts and returns the resulting string.
  2. Check if the resulting string from foo lexicographically smallest then assign a new string to the result.
if (r < res || res == "") res = r;

Upvotes: 1

Related Questions