Tuesday, 26 Oct 2021

# Lexicographically smallest string with given string as prefix

Given an array arr[] consisting of N strings and a string S if size M, the task is to find the lexicographically smallest string consisting of the string S as the prefix. If there doesn’t exist any string starting with prefix S then print “-1”.Examples:Input: arr[] = {“apple”, “appe”, “apl”, “aapl”, “appax”}, S = “app”Output: appaxExplanation:The lexicographical order of the strings consisting of “app” as the substring is {“aapl”, “apl”, “appax”, “appe”, “apple”}. The smallest lexicographic string containing is “appax”.Input: arr[] = {“can”, “man”, “va”}, S = “van”Output: -1Approach: The given problem can be solved by sorting the given array of strings arr[] such that all the strings starting with prefixes S occur consecutively. Now traverse the given array of strings arr[] and when the first string whose prefix matches with S then print that string and break out of the loop. Otherwise, print “-1”.Below is the implementation of the above approach:C++  #include using namespace std;  bool is_prefix(string temp, string str){        if (temp.length() < str.length())        return 0;    else {                          for (int i = 0;             i < str.length(); i++) {              if (str[i] != temp[i])                return 0;        }        return 1;    }}  string lexicographicallyString(    string input[], int n, string str){        sort(input, input + n);      for (int i = 0; i < n; i++) {        string temp = input[i];                                  if (is_prefix(temp, str)) {            return temp;        }    }              return "-1";}  int main(){    string arr[] = { "apple", "appe", "apl",                     "aapl", "appax" };    string S = "app";    int N = 5;      cout