Counting values inside string

Question

Today I stumbled upon an interesting task.

Create an algorithm that compress string with repeated symbols. 

"aaaaabbbbbbbbcd" -> "a5b8c1d1"
"abcaaaaaaaaaaaaaaaaaabbc" -> "a1b1c1a18b2c1"

if compressed string longer than original ("ab" -> "a1b1") return string without changes

I'm not strong in programming and can't really move an inch with this task. I tried to use Array and map but it's all not working. How can i start? Should i try with functions like map, filter, reduce or create func and implement logic inside? Any help will be appreciated !

There were examples only with letters, but according to logic it should be like this "a111" - > "a113" "aaaaaaaaaaaaa" -> "a13" — ofigensky
– ofigensky, Commented Jul 13, 2022 at 19:20
Did you try with a simple for loop? You could use reduce(into:_) too to do so. — Larme
– Larme, Commented Jul 13, 2022 at 19:28
This is called run-length encoding, by the way. I suggest you read the Software Engineering Open letter to students with homework problems — Alexander
– Alexander, Commented Jul 13, 2022 at 20:41

de. · Accepted Answer · 2022-07-13 22:45:13Z

Do it the simplest way possible: with a loop. No need to know fancy stuff like map and reduce for now, no need for intermediate data structures either.

Just iterate all characters and employ the logic in the loop (compare to previous character, count repetitions, etc...).
Then you may encounter special cases like for the first and last iteration and handle them appropriately.

Also you can't get faster than this, because you do only one iteration.

import Foundation

extension String {

    func compressed() -> String {
        
        var result = ""
        var counter = 1
        var storedChar: Character? = nil
        for (i, currentChar) in self.enumerated() {
            
            if storedChar == nil { // special case: first char
                
                storedChar = currentChar
            } else if storedChar == currentChar {
                
                counter += 1
            } else {
                
                result += String(storedChar!) + String(counter)
                storedChar = currentChar
                counter = 1
            }

            if i == self.count-1 { // special case: last char
                
                result += String(storedChar!) + String(counter)
            }
        }

        if result.count >= self.count {

            return self 
        }

        return result
    }
}


"aaaaabbbbbbbbcd".compressed() == "a5b8c1d1"
"abcaaaaaaaaaaaaaaaaaabbc".compressed() == "a1b1c1a18b2c1"
"ab".compressed() == "ab"

chux · Accepted Answer · 2022-07-13 19:43:51Z

1

Form a counter and compare the current character to the next on each iteration. Only print when current character differs from next.

// Pseudo code
s = "aaaaabbbbbbbbcd"

count = 1

while (s not at end) 
  c = *s
  advance s
  if c same as next
    increment count
  else 
    print c and count
    count = 1
end loop

edited Jul 13, 2022 at 19:43

answered Jul 13, 2022 at 19:30

chux

158k17 gold badges160 silver badges311 bronze badges

Comments

Larme · Accepted Answer · 2022-07-13 19:43:52Z

You can use reduce(into:_) to do so:

The logic is to keep an array (ie ordered), with letter, and its number of following occurence. You iterate over the String, and check last entry. Increment its value, or append it to the array. Then, you iterate over the reduce output, and create the final string.

func compressing(str: String) -> String {
    let reduced = str.reduce(into: [(Character, Int)]()) { result, current in
        guard var last = result.last else {
            result.append((current, 1))
            return
        }
        if last.0 == current {
            last = (current, last.1 + 1)
            result[result.count - 1] = last
        } else {
            result.append((current, 1))
        }
    }
    print(reduced)
    let output = reduced.map { String($0.0) + "\($0.1)" }.joined()
    if output.count > str.count {
        return str
    } else {
        return output
    }
}

To test it:

let values: [(String, String)] = [("aaaaabbbbbbbbcd", "a5b8c1d1"),
                                  ("abcaaaaaaaaaaaaaaaaaabbc", "a1b1c1a18b2c1"),
                                  ("a111", "a113"),
                                  ("aaaaaaaaaaaaa", "a13")]

values.forEach {
    let result = compressing(str: $0.0)
    print("\(result) \(result == $0.1 ? "=" : "!")= \($0.1)")
}

Output:

[("a", 5), ("b", 8), ("c", 1), ("d", 1)]
a5b8c1d1 == a5b8c1d1
[("a", 1), ("b", 1), ("c", 1), ("a", 18), ("b", 2), ("c", 1)]
a1b1c1a18b2c1 == a1b1c1a18b2c1
[("a", 1), ("1", 3)]
a113 == a113
[("a", 13)]
a13 == a13

Collectives™ on Stack Overflow

Counting values inside string

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related