{{ message }}

Instantly share code, notes, and snippets.

# ericnormand/00 Longest Alternating Substring.md

Last active Apr 10, 2022

Longest Alternating Substring

Write a function that takes a string of digits and returns the longest substring that contains only alternating odd/even digits. If two substrings have the same length, return the one that appears first.

Examples

```(longest-alt-subs "") ;=> ""
(longest-alt-subs "1") ;=> "1"
(longest-alt-subs "123") ;=> "123"
(longest-alt-subs "13") ;=> "1"
(longest-alt-subs "122381") ;=> "2381"```

Thanks to this site for the problem idea, where it is rated Expert in Python. The problem has been modified.

### jrwdunham commented Oct 11, 2021

```(defn longest-alt-prefs [input-string]
(loop [[new-char & rest-chars] input-string
new-dig (and new-char (Integer/parseInt (str new-char)))]
(if (or (and last-dig new-dig
(not= (even? last-dig) (even? new-dig)))
(and new-dig (not last-dig)))

(defn longest-alt-subs [input-string]
(->> (for [i (range (count input-string))]
(longest-alt-prefs (drop i input-string)))
(sort-by count)
(partition-by count)
last
first
(str/join "")))```

### steffan-westcott commented Oct 11, 2021 • edited

```(defn longest-alt-subs [s]
(if (empty? s)
""
(reduce (fn [a b] (max-key count b a))
(subs s 0 1)
(re-seq #"(?:)+?|(?:)+?" s))))```

### nbardiuk commented Oct 11, 2021 • edited

```(require '[clojure.string :as str])

(defn alternating-substrings [s]
(if (empty? s)
[s]
(->> (map vector s (range))
(partition-by (fn [[char index]]
;; since index alternates we can check if char follows index
;; this helps us to avoid checking alternation of neighbour chars
(= (even? (int char)) (even? index))))
(map #(str/join (map first %))))))

(defn first-longest [xs]
(apply (partial max-key count) (reverse xs)))

(defn longest-alt-subs [s]
(first-longest (alternating-substrings s)))```

### jonasseglare commented Oct 11, 2021

```(defn longest-alt-subs [s]
(->> (range (count s))
(partition-by #(even? (+ % (int (nth s %)))))
(map #(subs s (first %) (inc (last %))))
reverse
(apply max-key count "")))```

### miner commented Oct 11, 2021

```(defn longest-alt-subs [s]
(let [chodd? (fn [ch] (case ch (\1 \3 \5 \7 \9) true false))]
(if (< (count s) 2)
s
(->> (reduce (fn [res c]
(let [p (peek (peek res))]
(if (= (chodd? p) (chodd? c))
(conj res [c])
(conj (pop res) (conj (peek res) c)))))
[[(first s)]]
s)
rseq
(apply max-key count)
(apply str)))))```

### miner commented Oct 11, 2021 • edited

Somewhat faster to access chars by index in S. Refactored.

```(defn longest-alt-subs [s]
(let [iodd? (fn [i] (case (.charAt ^String s ^int i) (\1 \3 \5 \7 \9) true false))
len (.length ^String s)]
(if (< len 2)
s
(let [[longstart longend start]
(reduce (fn [lls i]
(if (not= (iodd? (dec i)) (iodd? i))
lls
(let [[longstart longend start] lls]
(if (> (- i start) (- longend longstart))
[start i i]
[longstart longend i]))))
[-1 -1 0]
(range 1 len))]
(if (> (- len start) (- longend longstart))
(subs s start)
(subs s longstart longend))))))```

### alex-gerdom commented Oct 11, 2021

```(defn longest-alt-subs [s]
(let [even-odd #"()*?"
odd-even #"()*?"
empty-str #""
pattern  (re-pattern (str even-odd "|" odd-even "|" empty-str))
alt-subs (->> (re-seq pattern s)
(map first))]
(reduce (fn [longest el]
(if (< (count longest) (count el))
el
longest))
""
alt-subs)))```

### mchampine commented Oct 12, 2021 • edited

```(defn longest-alt-subs [s]
(->> (take-while seq (iterate rest s))
(mapcat #(reductions conj [] %))
(filter #(apply = 1 (map count (partition-by odd? (map int %)))))
reverse
(apply max-key count "")
(apply str)))```

### KingCode commented Oct 14, 2021 • edited

EDIT
@mchampine, nice use of `rest` and `reductions` to generate windows!
I shamelessly copied your idea - interestingly this is the third of recent challenges
in which a `windows` function is handy:

```(defn windows
"Constructs a lazy seq of all contiguous subsequences of xs."
[xs]
(->> xs (iterate rest)
(sequence (comp (take-while seq)
(mapcat #(reductions conj [] %))
(map seq)
(filter identity)))
(cons ()) lazy-seq))

(defn alternating-subs? [xs]
(= (count xs)
(->> xs (sequence (comp (map int)
(partition-by odd?)))
count)))

(defn longest-alt-subs [digs]
(->> digs windows
(filter alternating-subs?)
(sort-by (comp - count))
first
(apply str)))```

### viesti commented Apr 9, 2022 • edited

```(defn char->long [c]
(- (long c) 48))

(defn longest-alternating-substring [s]
(let [{:keys [max-alts alts]} (reduce (fn [{:keys [max-alts alts] :as acc} [prev-char next-char]]
(if (or (and (odd? prev-char)
(even? next-char))
(and (even? prev-char)
(odd? next-char)))
(update acc :alts (fnil conj [prev-char]) next-char)
(-> acc
(update :max-alts #(if (> (count alts) (count %))
alts
%))
(assoc :alts nil))))
{}
(partition 2 1 (map char->long s)))]
(clojure.string/join "" (if (> (count alts) (count max-alts))
alts
max-alts))))
```

loop version

```(defn longest-alternating-substring-loop [s]
(loop [alts nil
max-alts nil
[[prev-char next-char :as item] & rest'] (partition 2 1 (map char->long s))]
(if-not item
(clojure.string/join "" (if (> (count alts) (count max-alts))
alts
max-alts))
(recur (when (or (and (odd? prev-char)
(even? next-char))
(and (even? prev-char)
(odd? next-char)))
(if (nil? alts)
[prev-char next-char]
(conj alts next-char)))
(if (> (count alts) (count max-alts))
alts
max-alts)
rest'))))```