Find the longest sequential same character array

Question

I am a new guy to Java. I want to find the longest sequential same character array in a input character arrays.

For example, this character array:

bddfDDDffkl

The longest is DDD. Next example:

rttttDDddjkl

The longest is tttt.

I use the following code to deal with this problem but I want to improve my code. Could you tell me if there are any edge cases here? For example, if there are two same length arrays (for example rtttgHHH, there are two longest: ttt and HHH), how to solve this situation?

My following code:

public class SeqSameChar {
 public static void main (String[] args) {
 int subLength = 0;
 Scanner sc = new Scanner(System.in);
 String[] num = null;
 num = sc.nextLine().split(" ");
 String[] number = new String[num.length];
 for(int i = 0; i< number.length;i++) {
 number[i] = String.valueOf(num[i]);
 }
 subLength =length(number,num.length); 
 System.out.println(subLength);
 for(int i = index; i < index+subLength; i++) {
 System.out.print(number[i]);
 }
 }
 public static int index; 
 //to calculate the longest contiguous increasing sequence 
 public static int length(String[] A,int size){ 
 if(size<=0)return 0; 
 int res=1; 
 int current=1; 
 for(int i=1;i<size;i++){ 
 if(A[i].equals(A[i-1])){ 
 current++; 
 } 
 else{ 
 if(current>res){ 
 index=i-current; 
 res=current; 
 } 
 current=1; 
 } 
 } 
 return res; 
 }
}

image about run my code

• Simon Forsberg: I tried to enter the string bddfDDDffkl at first, which didn't work as expected. Entering the string as b d d f D D D f f k l seemed to work though. Please make it clear how you expect the input.
• tktktk0711: Hi, thanks for your comment. I will make it clear how it input. when you input the char, please input it after a place.
• tktktk0711: I have showed the full work code as text at the beginning, please check it, I showed the image to prove that my code do work.
• Florian Schaetz: "For example, if there are two same length arrays (for example rtttgHHH, there are two longest: ttt and HHH), how to solve this situation?" That question can only be answered by one person: You. How should we know? It's your problem. We can help you solve it once you have decided, but we cannot decide for you. That's simply a problem of your problem description.
• burglarhobbit: @tktktk0711 I think I just answered that question yesterday on this post. And my code is working perfectly as you want. I just answered it here again in case you still need help.

Answer 1

The code has a bug:

q q q u u u u u u 
3
qqq

It should be

6
uuuuuu

• tktktk0711: Hi every one, since my code can't print all possible longest character arrays and there is a bug, I have improved it. please see the above posted code after the posted image, and I also created a class KV. please help me improve it.

Answer 2

You have inconsistent spacing, generally if you have 4 spaces for indentation, stick to it for the rest of the code, nothing is saved by not including it, and it makes it easier for other people to read.

The same idea for names, shortening them doesn't really give much other than saving a few bytes, and makes it much much harder to understand what goes on in a few months, so descriptive names are better, unless the abbr. is really obvious or defined

Below is your code with better spacing, and suggestions for better variable names, although the suggestions are not perfect, try and improve on them

public class SeqSameChar {
 public static void main(String[] args) {
 int longestSequenceLength = 0;
 Scanner scan = new Scanner(System.in);
 String[] input = null;
 input = scan.nextLine().split(" ");
 String[] characters = new String[input.length];
 for(int i = 0; i < characters.length; i++) {
 characters[i] = String.valueOf(input[i]);
 }
 longestSequenceLength = lengthOfLongestSequence(characters,input.length); 
 System.out.println(longestSequenceLength);
 for(int i = index; i < index + longestSequenceLength; i++) {
 System.out.print(characters[i]);
 }
 }
 public static int index;
 //to calculate the longest contiguous increasing sequence
 public static int lengthOfLongestSequence(String[] characters, int size){ 
 if(size <= 0) return 0; 
 int longestFound = 1; 
 int current = 1; 
 for(int i = 1; i < size; i++){ 
 if(characters[i].equals(characters[i-1])){ 
 current++; 
 } 
 else{ 
 if(current > longestFound){ 
 index = i - current; 
 longestFound = current; 
 } 
 current = 1; 
 } 
 } 
 return longestFound; 
 }
}

---

Next lets look at smaller parts

int longestSequenceLength = 0;

Why is this so far away from where it is used? Try to keep the declaration of variables to as near to their first use as possible

---

String[] input = null;
input = scan.nextLine().split(" ");

Good, but you don't need the null here

String[] input = scan.nextLine().split(" ");

---

String[] characters = new String[input.length];
 for(int i = 0; i < characters.length; i++) {
 characters[i] = String.valueOf(input[i]);
 }

This piece of code doesn't actually achieve anything, you are basically copying a String array to another String array, using an unnecessary parse too. Since it is not needed, you can just delete it, and change any later references in the code to it, to input instead.

---

lengthOfLongestSequence(characters,input.length);

This could have lead to a bug, since you are passing an array, and passing the length of another array. If someone ever changed either array between copying them and the call of this method, it would break.

There is no real need to pass the length of an array anyway, in Java it is easy enough to get, and isn't a costly operation

---

for(int i = index; i < index + longestSequenceLength; i++) {
 System.out.print(characters[i]);
}

Since it is going to be the same character, why do we need to loop over the array? We could just print the character once and it would serve the same purpose

---

public static int index; 

Huh? I didn't notice the global variable for quite a while, it looks like it is a method. I would move this to the top, above main.

It would not be good practice, but if I was being lazy, I would just print the character before returning the length of the longest sequence, or return an array or list with both in it, rather than using a global. I just prefer not to use global variables until I have to.

---

if(size <= 0) return 0;

If a negative size was passed in, it is really a cause for concern, so we should throw an exception here. If we don't pass in the size, there is no need to check for it, so we can just replace this with

int size = characters.length;

And everything works out

---

for(int i = 1; i < size; i++){ 
 if(characters[i].equals(characters[i-1])){ 
 current++; 
 } 
 else{ 
 if(current > longestFound){ 
 index = i - current; 
 longestFound = current; 
 } 
 current = 1; 
 } 
} 

There is a bug here, if you reach the end of the array, and the longest sequence is at the end, what happens? I'll leave it to you to figure out the fix.

A hint towards what I would do is try to add an extra check at the end

---

Spoiler below for code with all the changes, it is not the best, but hopefully it helps

public class SeqSameChar {
 public static int index;
 public static void main(String[] args) {
 Scanner scan = new Scanner(System.in);
 String[] input = scan.nextLine().split(" ");
 int longestSequenceLength = lengthOfLongestSequence(input);
 System.out.println(longestSequenceLength);
 System.out.println(input[index]);
 }
 //to calculate the longest contiguous increasing sequence
 public static int lengthOfLongestSequence(String[] characters){
 int size = characters.length;
 int longestFound = 1;
 int current = 1;
 for(int i = 1; i <= size; i++){
 if(i < size && characters[i].equals(characters[i-1])){
 current++;
 }
 else{
 if(current> longestFound){
 index = i - current;
 longestFound = current;
 }
 current = 1;
 }
 }
 return longestFound;
 }
 }

• tktktk0711: Firstly, thanks for your kind code and comment, after I check it, I will report it.
• tktktk0711: ,thanks for your help, and I am improving my code so that print all possible longest character arrays (if there are two longest,for example a b b c c). I will report it after I finish it, please help me improve it again.
• tktktk0711: Hi every one, since my code can't print all possible longest character arrays and there is a bug, I have improved it. please see the above posted code after the posted image, and I also created a class KV. please help me improve it.

Answer 3

About the situation where you have 2 different characters the same number of times, for that you have to run a for loop in reverse to identify the 2nd character. So if the 2nd character is not same as the first one identified, and also if its number of repetitions are the same, you print both the characters or else, just print the single character you find at the first for loop because both the characters are going to be same.

Run a reverse for loop like this given below in your length function after the first for loop. Make sure to reset the variables that you are going to use again. This will identify another position of the variable that is repeating maximum times. But since a function can only return 1 value, use this reverse algorithm in a different function and have what you want to achieve.

for(int i=size-1;i>0;i--){ 
 if(A[i].equals(A[i-1])){ 
 current++; 
 } 
 else{ 
 if(current>res){ 
 index=i-current; 
 res=current; 
 } 
 current=1; 
 } 
} 

Incase you need more reference, here is my own code which works exactly as you want but don't use this algorithm and implement it directly as it will limit your thinking of generating new algorithms your way.(Migrated from the same question you asked on this link at StackOverflow.

public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 System.out.println("Enter String 1: ");
 String A1 = sc.nextLine();
 MaxRepeat(A1);
}
public static void MaxRepeat(String A) {
 int count = 1;
 int max1 = 1;
 char mostrepeated1 = ' ';
 for(int i = 0; i < A.length()-1;i++) {
 char number = A.charAt(i);
 if(number == A.charAt(i+1)) {
 count++;
 if(count>max1) {
 max1 = count;
 mostrepeated1 = number;
 }
 continue;
 }
 count = 1;
 }
 count = 1;
 int max2 = 1;
 char mostrepeated2 = ' ';
 for(int i = A.length()-1; i>0; i--) {
 char number = A.charAt(i);
 if(number == A.charAt(i-1)) {
 count++;
 if(count>max2) {
 max2 = count;
 mostrepeated2 = number;
 }
 continue;
 }
 count = 1;
 }
 if((max1==max2) && (mostrepeated1==mostrepeated2)) {
 System.out.println("Most Consecutively repeated character is: " + mostrepeated1 + " and is repeated " + max1 + " times.");
 }
 else if((max1==max2) && (mostrepeated1!=mostrepeated2)) {
 System.out.println("Most continously repeated characters are: " + mostrepeated1 + " and " + mostrepeated2 + " and they are repeated " + max1 + " times");
 }
}

• janos: It's nice that you provided an alternative implementation. But this site is called Code Review for a reason: it's about reviewing posted code. Please add an explanation why your algorithm is better than the code in the question, and ideally point out any other mistakes you notice. Remember, an answer here must be primarily about the posted code in the question, not about how you solved it yourself.
• burglarhobbit: @janos Yes Sir. Actually this question was asked on this yesterday. And I answered it too. I will make sure to review codes instead of implemeting alternate algorithms which I did here. Thank You for clearing out the basics for me. :)
• janos: Sure thing! On Stack Overflow, your answer is slightly better, but still not great. It would be a magnitude better if you could include there a short explanation how it works, and point out the specific problem with the posted code. Ping me after you improved this post here, and that one on Stack Overflow, I'll be happy to circle back and upvote both
• burglarhobbit: @janos Edited and improved the explanation at both the websites. Please surely let me know if I missed something.
• janos: Hm, I still don't see how this is a review of the posted code. A review looks more like "you do X, which is inefficient because of Y, and can be done better, for example Z". Or, "you do X, which is not recommended, as it violates the good practice of Y. This is better: Z". Also note that one size doesn't fit all. The identical response on different sites to different questions is unlikely to be done with care.

Answer 4

I would try something like this:

import java.util.*;
public class LongestSequentialCharacter {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 Hashtable hash = scan(sc.nextLine().split(""));
 String mostFrequent = findLongest(hash, hash.keySet());
 System.out.println(mostFrequent);
 }
 static Hashtable scan(String[] num) {
 Hashtable longest = new Hashtable(0);
 for (int i = 0; i < num.length; ++i) {
 if (longest.containsKey(num[i])) {
 longest.put(num[i], ((int)longest.get(num[i]) + 1));
 } else {
 longest.put(num[i], 1);
 }
 }
 return longest;
 }
 static String findLongest(Hashtable hash, Set keys) {
 int maxVal = 0;
 String maxChar = null;
 int tempVal;
 for (Object key: keys) {
 if ((tempVal = (int)hash.get(key)) > maxVal) {
 maxChar = (String)key;
 maxVal = tempVal;
 }
 }
 return maxChar;
 }
}

There are other ways you could do this, but I think the idea is fairly sound. I took the liberty of moving away from the char array, but you could return to that easily if you need it somewhere in your program.

• tktktk0711: Firstly, thanks for your code and comments, now I am checking it.
• tktktk0711: Hi, I have checked your code, but there is an error. ((int)longest.get(num[i]) + 1)) and (int)hash.get(key)) places have an error: Cannot cast from Object to int. Anyway, thanks for your kind help!
• John Halbert: No, it ran fine on my machine. What version of java do you have installed? What changes did you make? Sorry.
• janos: This answer is mostly code, an alternative implementation, and not really a review of the post code. Please add an explanation of what the original code was doing wrong, and what makes this alternative better.
• John Halbert: You're right, I need to be more specific, there were major issues with the original implementation. I assumed the poster would take the time to read the code and make the comparison but it should be spelled out. And again, I hope we get a response on version and changes made. We upcast from an int to an Object, so the downcast should be no problem. This may be a versioning issue, but at the very least the only change that should have to be made is changing int to Integer. But I assumed this would be inferred as well. My mistake.