A factory machine records its activities using lowercase letters from 'a' to 'z'. Each letter represents one activity. For example, 'a' may mean idle, 'b' may mean loading material, 'c' may mean processing, and 'd' may mean inspecting the finished product.

Find the longest continuous activity pattern that appears at least twice in the machine's activity log.

Class

MachineActivityAnalyzer

Method

findLongestRepeatedPattern

String findLongestRepeatedPattern(String activityLog)

Parameters

• activityLog: The machine activities in the order they were recorded.

Returns

Return the longest continuous pattern that occurs at least twice in activityLog.

Return an empty string if no pattern appears more than once. If multiple longest patterns exist, return the one whose first occurrence starts at the lowest index.

Rules

• A pattern must contain consecutive characters from activityLog.
• Both occurrences must contain exactly the same activities in the same order.
• The occurrences are allowed to overlap.

Constraints

• 2 ≤ activityLog.length() ≤ 30,000
• activityLog contains only lowercase English letters from 'a' to 'z'.

Examples

Example 1

findLongestRepeatedPattern( activityLog = "abcdeabcx" )

Output: "abc"

The activity pattern "abc" appears at the beginning and later in the log. No longer pattern occurs twice.

Example 2

findLongestRepeatedPattern( activityLog = "fghijk" )

Output: ""

Every activity code appears only once, so no pattern is repeated.

Example 3

findLongestRepeatedPattern( activityLog = "mmmmmm" )

Output: "mmmmm"

The pattern "mmmmm" occurs starting at indices 0 and 1. The two occurrences overlap.

Example 4

findLongestRepeatedPattern( activityLog = "abmnabpqmn" )

Output: "ab"

Both "ab" and "mn" are repeated patterns of length 2. The first occurrence of "ab" starts earlier, so it is returned.

Example 5

findLongestRepeatedPattern( activityLog = "xyzabxyzcdxyz" )

Output: "xyz"

The pattern "xyz" occurs three times, and no longer continuous pattern is repeated.