Given a set of strings of the same length, we need to find the length of the longest string, which is a prefix string of at least two strings.
Examples:
Input: ["abcde", "abcsd", "bcsdf", "abcda", "abced"] Output: 4 Explanation: Longest prefix string is "abcd". Input: ["pqrstq", "pwxyza", "abcdef", "pqrstu"] Output: 5
Approach:
- Starting from the 0th position, iterate over every character and check if that character occurs in at least two of the strings at the current position or not.
- If it occurs, then recursively call on the next position. Otherwise,
- Update the max value by taking the current maximum with Current_position – 1.
- Finally, return the max value.
C++
// C++ program to find longest// string which is prefix string// of at least two strings#include<bits/stdc++.h>using namespace std;int max1=0;// Function to find Max length // of the prefixint MaxLength(vector<string> v, int i, int m){ // Base case if(i>=m) { return m-1; } // Iterating over all the alphabets for(int k = 0; k < 26; k++) { char c = 'a' + k; vector<string> v1; // Checking if char exists in // current string or not for(int j = 0; j < v.size(); j++) { if(v[j][i] == c) { v1.push_back(v[j]); } } // If atleast 2 string have // that character if(v1.size()>=2) { // Recursive call to i+1 max1=max(max1, MaxLength(v1, i+1, m)); } else { max1=max(max1, i - 1); } } return max1;}// Driver codeint main(){ // Initialising strings string s1, s2, s3, s4, s5; s1 = "abcde"; s2 = "abcsd"; s3 = "bcsdf"; s4 = "abcda"; s5 = "abced"; vector<string> v; // push strings into vectors. v.push_back(s1); v.push_back(s2); v.push_back(s3); v.push_back(s4); v.push_back(s5); int m = v[0].size(); cout<<MaxLength(v, 0, m) + 1<<endl; return 0;} |
Java
// Java program to find longest// String which is prefix String// of at least two Stringsimport java.util.*;class GFG{static int max1 = 0;// Function to find Max length // of the prefixstatic int MaxLength(Vector<String> v, int i, int m){ // Base case if(i>=m) { return m-1; } // Iterating over all the alphabets for(int k = 0; k < 26; k++) { char c = (char)('a' + k); Vector<String> v1 = new Vector<String>(); // Checking if char exists in // current String or not for(int j = 0; j < v.size(); j++) { if(v.get(j).charAt(i) == c) { v1.add(v.get(j)); } } // If atleast 2 String have // that character if(v1.size() >= 2) { // Recursive call to i+1 max1=Math.max(max1, MaxLength(v1, i + 1, m)); } else { max1=Math.max(max1, i - 1); } } return max1;}// Driver codepublic static void main(String[] args){ // Initialising Strings String s1, s2, s3, s4, s5; s1 = "abcde"; s2 = "abcsd"; s3 = "bcsdf"; s4 = "abcda"; s5 = "abced"; Vector<String> v = new Vector<String>(); // push Strings into vectors. v.add(s1); v.add(s2); v.add(s3); v.add(s4); v.add(s5); int m = v.get(0).length(); System.out.print(MaxLength(v, 0, m) + 1); }} // This code is contributed by shikhasingrajput |
Python3
# Python3 program to find longest# string which is prefix string# of at least two stringsmax1 = 0# Function to find max length # of the prefixdef MaxLength(v, i, m): global max1 # Base case if(i >= m): return m - 1 # Iterating over all the alphabets for k in range(26): c = chr(ord('a') + k) v1 = [] # Checking if char exists in # current string or not for j in range(len(v)): if(v[j][i] == c): v1.append(v[j]) # If atleast 2 string have # that character if(len(v1) >= 2): # Recursive call to i+1 max1 = max(max1, MaxLength(v1, i + 1, m)) else: max1 = max(max1, i - 1) return max1# Driver codeif __name__ == '__main__': # Initialising strings s1 = "abcde" s2 = "abcsd" s3 = "bcsdf" s4 = "abcda" s5 = "abced" v = [] # Push strings into vectors. v.append(s1) v.append(s2) v.append(s3) v.append(s4) v.append(s5) m = len(v[0]) print(MaxLength(v, 0, m) + 1)# This code is contributed by BhupendraSingh |
C#
// C# program to find longest// String which is prefix String// of at least two Stringsusing System;using System.Collections.Generic;class GFG{ static int max1 = 0;// Function to find Max length // of the prefixstatic int MaxLength(List<String> v, int i, int m){ // Base case if (i >= m) { return m - 1; } // Iterating over all the alphabets for(int k = 0; k < 26; k++) { char c = (char)('a' + k); List<String> v1 = new List<String>(); // Checking if char exists in // current String or not for(int j = 0; j < v.Count; j++) { if (v[j][i] == c) { v1.Add(v[j]); } } // If atleast 2 String have // that character if (v1.Count >= 2) { // Recursive call to i+1 max1 = Math.Max(max1, MaxLength(v1, i + 1, m)); } else { max1 = Math.Max(max1, i - 1); } } return max1;}// Driver codepublic static void Main(String[] args){ // Initialising Strings String s1, s2, s3, s4, s5; s1 = "abcde"; s2 = "abcsd"; s3 = "bcsdf"; s4 = "abcda"; s5 = "abced"; List<String> v = new List<String>(); // push Strings into vectors. v.Add(s1); v.Add(s2); v.Add(s3); v.Add(s4); v.Add(s5); int m = v[0].Length; Console.Write(MaxLength(v, 0, m) + 1); }} // This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program to find longest// string which is prefix string// of at least two stringslet max1=0;// Function to find Max length// of the prefixfunction MaxLength(v, i, m){ // Base case if(i>=m) { return m-1; } // Iterating over all the alphabets for(let k = 0; k < 26; k++) { let c = String.fromCharCode('a'.charCodeAt(0) + k); let v1 = []; // Checking if char exists in // current string or not for(let j = 0; j < v.length; j++) { if(v[j][i] == c) { v1.push(v[j]); } } // If atleast 2 string have // that character if(v1.length >= 2) { // Recursive call to i+1 max1 = Math.max(max1, MaxLength(v1, i+1, m)); } else { max1 = Math.max(max1, i - 1); } } return max1;}// Driver code// Initialising stringslet s1, s2, s3, s4, s5; s1 = "abcde";s2 = "abcsd";s3 = "bcsdf";s4 = "abcda";s5 = "abced"; let v = []; // push strings into vectors.v.push(s1);v.push(s2);v.push(s3);v.push(s4);v.push(s5); let m = v[0].length; document.write(MaxLength(v, 0, m) + 1 + "<br>");</script> |
Output:
4
Time Complexity: O(N*26)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
