如何在O(n)的时间内输出包含数组元素（压缩不连续的重复项）的字符串？

问题：给定一个可能包含非连续重复元素的数组，如何输出一个字符串以按它们出现的顺序显示数量？

这里有一点解释，请跳到下面看我的问题。我曾经遇到一个问题，要输出有序数组中的重复连续字符串，以便在给定数组时，新字符串将按数量输出。

给定：

local Items = {"Wood", "Wood", "Wood", "Rope", "Rope"}

输出将是：

3x Wood 2x Rope

我的方法是遍历数组并检查相邻元素是否相等。然后我会将计数器递增并添加到字符串中。

local unpackedItems = ""
local index = 1
while index <= #Items do
    local count = 1
    while Items[index] == Items[index + 1] do
        count = count + 1
        index = index + 1
    end
    unpackedItems = unpackedItems .. count .. "x " .. Items[index] .. " "
    index = index + 1
end
print(unpackedItems)

这很好用，但我想知道它是否可以更好。

我的问题再次是非连续重复怎么办？给定一个可能包含重复元素的数组，如何输出一个字符串以按它们出现的顺序显示数量？

给定：

local Items = {"Wood", "Wood", "Wood", "Rope", "Rope", "Wood"}

输出：

4x Wood 2x Rope

我的解决方案是遍历数组并检查其他元素，并将已检查的索引存储在哈希表中。

local unpackedItems = ""
local checked = {}
local index = 1
while index <= #Items do
    if not checked[index] then
        local count = 1
        local currentItem = Items[index]
        for index2 = index + 1, #Items do
            if not checked[index2] and currentItem == Items[index2] then
                checked[index2] = true
                count = count + 1
            end
        end
        unpackedItems = unpackedItems .. count .. "x " .. Items[index] .. " "
    end
    index = index + 1
end
print(unpackedItems)

有没有更好的方法来实现这个问题，例如时间复杂度为O(n)? 并不太注重空间复杂度。

此外，每次将字符串连接起来会很昂贵，尤其是对于较大的字符串来说？

我没有使用哈希表来表示数据或向其转换的原因是它会失去它出现的原始顺序。我考虑的另一个解决方案是将表转换为字符串并像那样操作，但这不会将每个元素视为自己的实体。我希望防止名称“冲突”，因为“Wood”和“Fire Wood”可能不会被分开处理。

所使用的语言是Lua，但我也很想看看其他语言的解决方案。