Business Move Problem in Java
In this article, we will discuss how to write a Java program to determine the minimum number of moves required to make all strings equal.
Problem Statement
Given an array of n strings, we need to find the minimum number of operations required to make all the strings equal. An operation is defined as either adding a character to the end of a string or deleting a character from the end of a string. We can perform any number of operations on any string.
Approach:
To solve this problem, we can start by comparing the first character of all the strings in the array. If all the strings have the same first character, we can remove the first character from all the strings and continue this process until all the strings are equal. We can count the number of operations performed in this process and return the value as the result.
If the first character of all the strings is not the same, we can try adding the missing character to the shorter strings or removing the extra character from the longer strings. We can then compare the first character of all the strings again and repeat the process until all the strings are equal. We can count the number of operations performed in this process and return the value as the result.
Algorithm:
- Initialize n as the number of strings in the strings array, and result as 0.
- Loop infinitely: Initialize i to 0 and c to the first character of the first string in the strings array.
a. Initialize i to 0
b. While i is less than n and the length of the ith string is greater than 0 and the first character of the ith string is equal to c, increment i.
c. If i is equal to n, remove the first character from each string in the strings array and increment result.
d. Else, initialize j to 0.
e. While j is less than n and the length of the jth string is greater than 0 and the first character of the jth string is not equal to c, increment j.
f. If j is equal to n, return -1.
g. Else, count the number of strings that start with c and the number of strings that do not start with c.
h. If the number of strings that do not start with c is less than the number of strings that start with c, prepend c to each string that does not start with c and increment result by the number of strings that do not start with c.
i. Else, remove the first character from each string that starts with c and increment result by the number of strings that start with c.
j. Check if all strings in the strings array are equal. If they are, break out of the loop.
- Return result.
Here is the Java program to solve this problem:
Businessmove.java
import java.util.*;
public class Businessmove {
public static int minMoves(String[] strings) {
int n = strings.length;
int result = 0;
while (true) {
int i = 0;
char c = strings[0].charAt(0);
while (i < n && strings[i].length() > 0 && strings[i].charAt(0) == c) {
i++;
}
if (i == n) {
for (i = 0; i < n; i++) {
strings[i] = strings[i].substring(1);
}
result++;
} else {
int j = 0;
while (j < n && strings[j].length() > 0 && strings[j].charAt(0) != c) {
j++;
}
if (j == n) {
return -1;
}
int add = 0;
int remove = 0;
for (i = 0; i < n; i++) {
if (strings[i].length() == 0) {
continue;
}
if (strings[i].charAt(0) == c) {
remove++;
} else {
add++;
}
}
if (add < remove) {
for (i = 0; i < n; i++) {
if (strings[i].charAt(0) != c) {
strings[i] = c + strings[i];
}
}
result += add;
} else {
for (i = 0; i < n; i++) {
if (strings[i].charAt(0) == c) {
strings[i] = strings[i].substring(1);
}
}
result += remove;
}
}
boolean equal = true;
for (i = 1; i < n; i++) {
if (!strings[i].equals(strings[0])) {
equal = false;
break;
}
}
if (equal) {
break;
}
}
return result;
}
public static void main(String[] args) {
String[] strings = {"abc", "def", "ghi"};
int result = minMoves(strings);
if (result == -1) {
System.out.println("It is not possible to make all strings equal.");
} else {
System.out.println("Minimum number of moves to make all strings equal: " + result);
}
}
}
Output
It is not possible to make all strings equal.
Complexity:
In the worst case, the algorithm may have to iterate over all characters of all strings, which makes the time complexity O(N*L), where N is the number of strings and L is the maximum length of a string in the array.