Redistribute Characters to Make All Strings Equal

🏠 ⬅️ ➡️

You are given an array of strings words (0-indexed).

In one operation, pick two distinct indices i and j, where words[i] is a non-empty string, and move any character from words[i] to any position in words[j].

Return true if you can make every string in words equal using any number of operations, and false otherwise.

Example 1:

Input: words = [ "abc ", "aabc ", "bc "] Output: true Explanation: Move the first 'a' in words[1] to the front of words[2], to make words[1] = "abc " and words[2] = "abc ". All the strings are now equal to "abc ", so return true.

Example 2:

Input: words = [ "ab ", "a "] Output: false Explanation: It is impossible to make all the strings equal using the operation.

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j
    logical :: result
    character(len=:), allocatable :: words(:)

    words = ["abc ", "aabc ", "bc "]
    result = canMakeEqual(words)
    print "(L1)", result

    words = ["ab ", "a "]
    result = canMakeEqual(words)
    print "(L1)", result

contains

    function canMakeEqual(words) result(result)
        implicit none
        character(len=:), allocatable :: words(:)
        logical :: result
        integer :: i, j

        do i = 1, size(words) - 1
            do j = i + 1, size(words)
                if (words(i) /= "" .and. words(j) /= "") then
                    exit
                end if
            end do
            if (j == size(words)) then
                cycle
            end if

            do while (words(i) /= words(j))
                call moveChar(words, i, j)
            end do
        end do

        result = all(words == words(1))
    end function canMakeEqual

    subroutine moveChar(words, i, j)
        implicit none
        character(len=:), allocatable :: words(:)
        integer :: i, j
        character :: c

        c = words(i)(1:1)
        words(i) = words(i)(2:) // c
        words(j) = c // words(j)
    end subroutine moveChar
end program main
✅ Compiled
❌ Executed
❌ Correct 
program Equal_Strings
      implicit none

      integer, parameter :: MAX_LENGTH = 100
      integer :: n, i, j, k
      character(len=MAX_LENGTH) :: words(MAX_LENGTH)
      logical :: equal

      ! Read the number of words
      read(*,*) n

      ! Read the words
      do i = 1, n
         read(*,*) words(i)
      end do

      ! Initialize the equal flag
      equal = .true.

      ! Check if all the words are equal
      do i = 1, n-1
         do j = i+1, n
            if (words(i) /= words(j)) then
               equal = .false.
               exit
            end if
         end do
         if (.not. equal) exit
      end do

      ! If all the words are equal, print "True"
      ! Otherwise, print "False"
      if (equal) then
         print *, "True"
      else
         print *, "False"
      end if

      end program Equal_Strings
🌐 Data from online sources 
def longestPalindromeSubseq(word1, word2):
    n, m = len(word1), len(word2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n):
        for j in range(m):
            if word1[i] == word2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

    return dp[n][m]
  1. Create a 2D array dp of size (word1.length + 1) x (word2.length + 1) to store the longest common subsequence for each prefix of word1 and word2.
  2. Initialize all elements of dp to 0.
  3. Iterate through each character in word1 and word2.
  4. If the characters at position i in word1 and j in word2 are equal, update dp[i + 1][j + 1] to dp[i][j] + 1.
  5. If the characters are not equal, update dp[i + 1][j + 1] to the maximum of dp[i][j + 1] and dp[i + 1][j].
  6. Return the value at dp[word1.length][word2.length], which is the length of the longest palindrome subsequence between word1 and word2.
🌐 Data from online sources 
#include <string>
using namespace std;

int longestPalindromeSubseq(string word1, string word2) {
    int n = word1.length();
    int m = word2.length();

    int dp[1001][1001] = {0};

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (word1[i] == word2[j]) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
            } else {
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
            }
        }
    }

    return dp[n][m];
}
  1. Create a 2D array dp of size (word1.length + 1) x (word2.length + 1) to store the longest common subsequence for each prefix of word1 and word2.
  2. Initialize all elements of dp to 0.
  3. Iterate through each character in word1 and word2.
  4. If the characters at position i in word1 and j in word2 are equal, update dp[i + 1][j + 1] to dp[i][j] + 1.
  5. If the characters are not equal, update dp[i + 1][j + 1] to the maximum of dp[i][j + 1] and dp[i + 1][j].
  6. Return the value at dp[word1.length][word2.length], which is the length of the longest palindrome subsequence between word1 and word2.