You Are Given a WASD-string... (Codeforces 1202C)
Tags: Greedy, strings

You have a string $$$s$$$ — a sequence of commands for your toy robot. The robot is placed in some cell of a rectangular grid. He can perform four commands:  'W' — move one cell up;  'S' — move one cell down;  'A' — move one cell left;  'D' — move one cell right. Let $$$Grid(s)$$$ be the grid of minimum possible area such that there is a position in the grid where you can place the robot in such a way that it will not fall from the grid while running the sequence of commands $$$s$$$. For example, if $$$s = \text{DSAWWAW}$$$ then $$$Grid(s)$$$ is the $$$4 \times 3$$$ grid:  you can place the robot in the cell $$$(3, 2)$$$;  the robot performs the command 'D' and moves to $$$(3, 3)$$$;  the robot performs the command 'S' and moves to $$$(4, 3)$$$;  the robot performs the command 'A' and moves to $$$(4, 2)$$$;  the robot performs the command 'W' and moves to $$$(3, 2)$$$;  the robot performs the command 'W' and moves to $$$(2, 2)$$$;  the robot performs the command 'A' and moves to $$$(2, 1)$$$;  the robot performs the command 'W' and moves to $$$(1, 1)$$$.   You have $$$4$$$ extra letters: one 'W', one 'A', one 'S', one 'D'. You'd like to insert at most one of these letters in any position of sequence $$$s$$$ to minimize the area of $$$Grid(s)$$$.What is the minimum area of $$$Grid(s)$$$ you can achieve?

Input: The first line contains one integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of queries.Next $$$T$$$ lines contain queries: one per line. This line contains single string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$, $$$s_i \in \{\text{W}, \text{A}, \text{S}, \text{D}\}$$$) — the sequence of commands.It's guaranteed that the total length of $$$s$$$ over all queries doesn't exceed $$$2 \cdot 10^5$$$.

Output: Print $$$T$$$ integers: one per query. For each query print the minimum area of $$$Grid(s)$$$ you can achieve.

Note: In the first query you have to get string $$$\text{DSAWW}\underline{D}\text{AW}$$$.In second and third queries you can not decrease the area of $$$Grid(s)$$$.

Sample Inputs:
3
DSAWWAW
D
WA

Sample Outputs:
8
2
4

Solution (Python):
def main():
    (h, v) = hv = ([0], [0])
    f = {'W': (v, -1), 'S': (v, 1), 'A': (h, -1), 'D': (h, 1)}.get
    for _ in range(int(input())):
        del h[1:], v[1:]
        for (l, d) in map(f, input()):
            l.append(l[-1] + d)
        x = y = 1
        for l in hv:
            (lh, a, n) = ((min(l), max(l)), 200001, 0)
            for b in filter(lh.__contains__, l):
                if a != b:
                    a = b
                    n += 1
            le = lh[1] - lh[0] + 1
            (x, y) = (y * le, x * (le - (n < 3 <= le)))
        print(x if x < y else y)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
import heapq

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    s = readStr()
    (a, b) = ([0], [0])
    for c in s:
        if c == 'A':
            a.append(a[-1] + -1)
        elif c == 'D':
            a.append(a[-1] + 1)
        elif c == 'W':
            b.append(b[-1] + -1)
        else:
            b.append(b[-1] + 1)
    (mia, maa) = (min(a), max(a))
    (mib, mab) = (min(b), max(b))
    ans = (maa - mia + 1) * (mab - mib + 1)
    for _ in range(2):
        (j, k) = (a.index(mia), a.index(maa))
        v0 = v1 = 0
        for i in range(1, len(a)):
            if i == j:
                v0 = max(v0, a[i - 1] + 1, max(a[i:]) + 1)
                ans = min(ans, (v0 - mia) * (mab - mib + 1))
            if i == k:
                v1 = min(v1, a[i - 1] - 1, min(a[i:]) - 1)
                ans = min(ans, (maa - v1) * (mab - mib + 1))
            v0 = max(v0, a[i])
            v1 = min(v1, a[i])
        a = b
        (mib, mab, mia, maa) = (mia, maa, mib, mab)
    return ans
for _ in range(int(input())):
    print(solve())

Solution (Python):
def main():
    (hh, vv, r) = ([0], [0], [])
    f = {'W': (vv, -1), 'S': (vv, 1), 'A': (hh, -1), 'D': (hh, 1)}.get
    for _ in range(int(input())):
        del vv[1:], hh[1:], r[:]
        for (l, d) in map(f, input()):
            l.append(l[-1] + d)
        for l in (hh, vv):
            (mi, ma) = (min(l), max(l))
            (a, tmp) = (mi - 1, [])
            for b in filter((mi, ma).__contains__, l):
                if a != b:
                    a = b
                    tmp.append(a)
            ma -= mi - 1
            r.append(ma)
            if len(tmp) < 3 <= ma:
                ma -= 1
            r.append(ma)
        print(min((r[0] * r[3], r[1] * r[2])))
if __name__ == '__main__':
    main()