Getting terminate called after throwing an instance of 'std::length_error'

Question

I am getting this above error and I am unable to debug the cause for it. Can anyone help me with this (what's causing this error)?

Problem Statement: Finding Longest Common Prefix

Source: https://leetcode.com/problems/longest-common-prefix/

Code(Using Divide and Conquer):

#include <iostream>
#include <unordered_map>
#include <string> 
#include <vector>

using namespace std;
class Solution {
public:
    string common_prefix(string left, string right){       
        int minim = min(left.length(), right.length());
        for (int i=0; i<minim; i++){
            if (left[i]!=right[i]){
                return left.substr(0, i);
            }
        }
        return "" ;
    }
    string dap(vector<string>& a, int l, int r){
        if (l==r) return a[l];    

        int mid = (l+r)/2;
        string left = dap(a, l, mid);
        string right = dap(a, mid+1, r);
        return common_prefix(left, right);
    }
    string longestCommonPrefix(vector<string>& strs) {

        
        return dap(strs, 0, strs.size());
        
    }
};


int main()
{
    Solution s;
    vector<string> st{"flower","flow","flight"};
    string ans = s.longestCommonPrefix(st);
    cout << ans;
}

Traceback:

Runtime Error
terminate called after throwing an instance of 'std::length_error'
  what():  basic_string::_M_create

Input:

["flower","flow","flight"]

Expected Output:

"fl"

link: https://ide.geeksforgeeks.org/9nKPmtFPd5

Answer 1

You have two issues in your code.

1. your initial value for r is strs.size(), after a few recursions you get to the line if (l == r) return a[l]; with r still at its initial value. a[a.size()] leads to undefined behaviour. The initial value for r should be strs.size() - 1.

2. In common_prefix if the whole of the shorter string is the prefix of the longer one you return an empty string. You should return left.substr(0, minim) instead.

For efficiency you should use const string& left instead of string left in your function parameters to avoid copying the strings. You could also use std::string_view to avoid copying strings at all:

#include <iostream>
#include <string> 
#include <vector>
#include <string_view>

class Solution {
public:
    std::string_view common_prefix(const std::string_view& left, const std::string_view& right) {
        int minim = std::min(left.length(), right.length());
        for (int i = 0; i < minim; i++) {
            if (left[i] != right[i]) {
                return left.substr(0, i);
            }
        }
        return left.substr(0, minim);
    }

    std::string_view dap(const std::vector<std::string>& a, int l, int r) {
        if (l == r) return a[l];

        int mid = (l + r) / 2;
        std::string_view left = dap(a, l, mid);
        std::string_view right = dap(a, mid + 1, r);
        return common_prefix(left, right);
    }

    std::string_view longestCommonPrefix(const std::vector<std::string>& strs) {
        return dap(strs, 0, strs.size()-1);
    }
};


int main()
{
    Solution s;
    std::vector<std::string> st{ "flower","flow","flight" };
    std::string_view ans = s.longestCommonPrefix(st);
    std::cout << ans;
}

Answer 2

std::length_error means you are trying to create a string longer than std::string::max_size()

Therefore you need to track the string that throws via. try/catch