Algorithm: Optimally splitting a string into 3 substrings

Question

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.

If it helps, this is just a lot of extra baggage surrounding a description of 3-way partition.. A string is just an array of characters, after all. — Putnam
– Putnam, Commented Jun 28, 2020 at 16:02
The problem always guarantees that there will be a solution so k1, k2, k3 >= 1 and cannot be empty. — emufan4568
– emufan4568, Commented Jun 28, 2020 at 16:23

Aleksey Kuchkin · Accepted Answer · 2020-06-29 12:39:04Z

1

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:

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++)

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)};

Сall the function foo which reverse each substring, concatenate the three parts and returns the resulting string.
Check if the resulting string from foo lexicographically smallest then assign a new string to the result.

if (r < res || res == "") res = r;

edited Jun 29, 2020 at 12:39

answered Jun 28, 2020 at 16:51

Aleksey Kuchkin

1431 silver badge5 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Aleksey Kuchkin Over a year ago

@גלעד ברקן After editing, the output became correct. For input: "bndakonda" the output should be "adnbdnoka".

Collectives™ on Stack Overflow

Algorithm: Optimally splitting a string into 3 substrings

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related