Longest Repeated Sub-sequence

 

 

Given a string, print the longest repeating sub-sequence such that the two sub-sequence don’t have same string character at same position, i.e., any i’th character in the two sub-sequences shouldn’t have the same index in the original string.

 

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map;   public class RepeatedSubsequence {    public static void main(String[] args) {   String str = "AABEBCDD";   RepeatedSubsequence rr = new RepeatedSubsequence();   System.out.println(rr.repeatedSubsequence(str));  }    public String repeatedSubsequence(String data) {   Map<Character, Character> map = new HashMap<Character, Character>();   List<Character> list = new ArrayList<Character>();     char[] X = data.toCharArray();   for (char c : X) {    if (!map.containsValue(c)) {     map.put(c, c);    } else {     if(!list.contains(c)){     list.add(c);     }    }   }   StringBuffer br = new StringBuffer();   for (char d : list) {    br.append(d);   }     return br.toString();    } }

 

The Java code you provided is designed to find and return the characters that are repeated in a given string as a subsequence. Here’s a breakdown of how it works:

Explanation:

1. Initialization:
• A HashMap named map is used to keep track of characters that have already been encountered in the string.
• A List named list is used to store characters that are repeated.
2. Loop Through Characters:
• The string is converted to a character array X.
• For each character in X, the code checks if the character is already present in the map:
• If it’s not in the map, it is added.
• If it is in the map and is not already in the list, it is added to the list.
3. Build the Result:
• A StringBuffer named br is used to concatenate the characters from the list.
• The final string, which contains the repeated characters, is returned.

Example:

Given the input string "AABEBCDD", the program will process it as follows:

• 'A' is encountered first and added to the map.
• 'A' is encountered again, and since it’s already in the map, it's added to the list.
• 'B' is encountered and added to the map.
• 'E' is encountered and added to the map.
• 'B' is encountered again, and since it’s already in the map, it's added to the list.
• 'C' is encountered and added to the map.
• 'D' is encountered and added to the map.
• 'D' is encountered again, and since it’s already in the map, it's added to the list.

The resulting string of repeated characters is "ABD".

Output:

When you run the code with the input "AABEBCDD", the output will be:

java

ABD

 

This string contains the characters that appear more than once in the input string.

  

Longest Repeated Sub-sequence