Longest Common Prefix in an Array of Strings

Posted by N.K. Chauhan on Mar 31, 2024

Given an array, arr[] of "n" different strings, the task is to find the longest common prefix among all strings present in the array.

Input: {"cup", "cupboard", "cut", "curse"}, Output: "cu"

Input: {"hit", "duper", "super"}, Output: "-1"


Method 1: In O(n * length of prefix) time and O(1) space

The idea is to first calculate the length of shortest string, because the common prefix can not exceed the length of shortest string.

Next, start a loop from "0" to "length of shortest string", and in each iteration check if the ith character is same in each string.

If ith character is same in each string, than this character will be part of common prefix.

Else if in any iteration the ith character is different for any string, return substring of any string from 0 to i.


The time complexity of this solution is O(n * length of prefix) and space complexity is O(N).


Find all substrings of a string in "O (n^2)" time

Swap all occurrences of two characters to get lexicographically smallest string

Check whether the given string is a palindrome

Print all permutations of a given string

Reverse words in a given string

Check if two given strings are isomorphic to each other

Check if two strings are equal or not after processing backspace

Transform One String to Another with a Minimum Number of Operations

Power Set: Print all non-empty subsequences of a string

Print all subsequences of a string