Count Consecutive Duplicate Lines
Problem
Like the Unix command uniq -c: group lines that are equal and next to each other. For every group print its size, a space, and the line. Equal lines that are not next to each other are different groups.
Constraints
- 1 <= lines <= 10^4
Examples
Input
a a b b b a
Output
2 a 3 b 1 a
Solutions
A counter follows the current line. When the line changes we write the finished group. Only one pass and O(1) extra state.
/*
* Problem : Process lines.
* Input : Several lines.
* Output : One line per group.
* Approach: Running counter.
* Time : O(n)
* Space : O(1) extra
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
// Step 1: Keep the current line and how many times in a row it was seen.
java.util.List<String> result = new java.util.ArrayList<String>();
String current = lines[0];
int count = 1;
for (int i = 1; i < lines.length; i++) {
if (lines[i].equals(current)) {
count++;
} else {
// Step 2: A different line closes the group.
result.add(count + " " + current);
current = lines[i];
count = 1;
}
}
result.add(count + " " + current);
return result.toArray(new String[0]);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
java.util.List<String> all = new java.util.ArrayList<>();
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (!line.isEmpty()) {
all.add(line);
}
}
String[] lines = all.toArray(new String[0]);
System.out.println(String.join("\n", solve(lines)));
}
}
Hints (2)
- When do we write a group?
- Why is the last group written after the loop?