Find the longest string

JavaView on GFG

Intuition

Find longest string in array that is a subsequence of all other strings (or similar constraint).

Algorithm

1Sort by length. For each string: check if it is subsequence of others. Return longest valid one.

Common Pitfalls

•Check each candidate string as subsequence of target string. O(n*m) total.

Find the longest string.java

Java

// Approach: Linear scan tracking maximum length string seen so far.
// Time: O(n * len) Space: O(1)
import java.util.*;

class Solution {
    public String longestString(String[] arr) {
        // Sort by length ascending, then lexicographically
        Arrays.sort(arr, (a, b) -> {
            if (a.length() == b.length())
                return a.compareTo(b);
            return a.length() - b.length();
        });

        Set<String> set = new HashSet<>();
        String answer = "";

        for (String word : arr) {
            // If word is 1 char or its immediate prefix is valid
            if (word.length() == 1 || set.contains(word.substring(0, word.length() - 1))) {
                set.add(word);
                if (word.length() > answer.length() ||
                        (word.length() == answer.length() && word.compareTo(answer) < 0))
                    answer = word;

            }
        }

        return answer.isEmpty() ? "-1" : answer;
    }
}

Was this solution helpful?