Knowee
Questions
Features
Study Tools

Internship Alert!New month-> Fresh Chance to top the leaderboard and get SDE Internship! Given a string s of length n, find the longest repeating non-overlapping substring in it. In other words find 2 identical substrings of maximum length which do not overlap. Return the longest non-overlapping substring. Return "-1" if no such string exists.Note: Multiple Answers are possible but you have to return the substring whose first occurrence is earlier.For Example: "abhihiab", here both "ab" and "hi" are possible answers. But you will have to return "ab" because it's first occurrence appears before the first occurrence of "hi".

Question

Internship Alert!New month-> Fresh Chance to top the leaderboard and get SDE Internship! Given a string s of length n, find the longest repeating non-overlapping substring in it. In other words find 2 identical substrings of maximum length which do not overlap. Return the longest non-overlapping substring. Return "-1" if no such string exists.Note: Multiple Answers are possible but you have to return the substring whose first occurrence is earlier.For Example: "abhihiab", here both "ab" and "hi" are possible answers. But you will have to return "ab" because it's first occurrence appears before the first occurrence of "hi".

...expand
🧐 Not the exact question you are looking for?Go ask a question

Solution

Sure, I can help with that. Here's a step-by-step solution to the problem:

  1. Initialize a variable max_length to 0 and res_string to an empty string. These will keep track of the maximum length of the repeating non-overlapping substring and the substring itself.

  2. Create a 2D array dp of size n x n where n is the length of the string. This will be used to store the length of the longest repeating non-overlapping substring ending at indices i and j.

  3. Iterate over the string from the end. For each character at index i, iterate over all characters at index j where j < i.

  4. If the characters at indices i and j are the same, then dp[i][j] is 1 + dp[i+1][j+1]. However, we need to ensure that the substrings do not overlap. So, we only update dp[i][j] if dp[i+1][j+1] < (j - i). This ensures that the next character of the substring ending at i is not the same as the next character of the substring ending at j.

  5. If the characters at indices i and j are not the same, then dp[i][j] is 0.

  6. If dp[i][j] is greater than max_length, update max_length and res_string.

  7. After the iterations, res_string will be the longest repeating non-overlapping substring.

  8. If max_length is still 0, return "-1". Otherwise, return res_string.

This solution works by finding all repeating non-overlapping substrings and keeping track of the longest one. The 2D array dp is used to store the lengths of the longest repeating non-overlapping substrings ending at each pair of indices. The condition dp[i+1][j+1] < (j - i) ensures that the substrings do not overlap.

This problem has been solved

Similar Questions

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Given a string s, find the length of the longest substring without repeating characters. Example 1:Input: s = "abcabcbb"Output: 3Explanation: The answer is "abc", with the length of 3.Example 2:Input: s = "bbbbb"Output: 1Explanation: The answer is "b", with the length of 1.Example 3:Input: s = "pwwkew"Output: 3Explanation: The answer is "wke", with the length of 3.Notice that the answer must be a substring, "pwke" is a subsequence and not a substring. Constraints:0 <= s.length <= 5 * 104s consists of English letters, digits, symbols and spaces.

Raju is preparing questions for the internal test. While creating questions, he gave one such question to his son Arun to solve. Raju has given the string S to his son Arun. Arun's task is to print the size of the longest possible substring that has exactly K unique characters.ExampleInput:String = aabacbebebe; K = 3Output:The substring will be cbebebe with length 7. Explanation:The unique characters in the string are: 'a', 'b', 'c', and 'e'. The longest subsequence with at most 3 distinct characters is "aabacbe". It contains the characters 'a', 'b', and 'c', which is the maximum number of distinct characters allowed (k = 3). Therefore, the length of the longest subsequence is 7.Input format :The first line of input consists of the string S.The second line of input consists of the integer K.Output format :The output prints the size of the longest possible substring that has exactly K unique characters.Refer to the sample output for the formatting specifications.Code constraints :1≤ string length ≤ 501≤ K ≤10Sample test cases :Input 1 :aabacbebebe3Output 1 :7Input 2 :abbc1Output 2 :2

Write a function:class Solution { public int solution(String S); }that, given a string S consisting of N lowercase English letters, returns the length of the longest substring in which every letter occurs an even number of times. A substring is defined as a contiguous segment of a string. If no such substring exists, return 0.Examples:1. Given S = "bdaaadadb", the function should return 6. Substrings in which every letter occurs an even number of times are "aa", "adad", "daaada" and "aaadad". The length of the longest of them is 6.2. Given S = "abacb", the function should return 0. There is no non-empty substring in which every letter occurs an even number of times.3. Given S = "zthtzh", the function should return 6. Every letter in the whole string occurs an even number of times.Write an efficient algorithm for the following assumptions:N is an integer within the range [1..100,000];string S consists only of lowercase letters ('a'-'z').

1/3

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.