Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
446 PurelyFunctional.tv Newsletter

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.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

@jrwdunham
Copy link

jrwdunham commented Oct 11, 2021

(defn longest-alt-prefs [input-string]
  (loop [[new-char & rest-chars] input-string
         answer []]
    (let [last-dig (last answer)
          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)))
        (recur rest-chars (conj answer new-dig))
        answer))))

(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
Copy link

steffan-westcott commented Oct 11, 2021

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

@nbardiuk
Copy link

nbardiuk commented Oct 11, 2021

(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
Copy link

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
Copy link

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
Copy link

miner commented Oct 11, 2021

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
Copy link

alex-gerdom commented Oct 11, 2021

(defn longest-alt-subs [s]
  (let [even-odd #"([02468][13579])*[02468][13579]?"
        odd-even #"([13579][02468])*[13579][02468]?"
        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
Copy link

mchampine commented Oct 12, 2021

(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
Copy link

KingCode commented Oct 14, 2021

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
Copy link

viesti commented Apr 9, 2022

(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'))))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment