LeetCode 471 - Encode String with Shortest Length


Related: LeetCode 394 - Decode String
http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/
Given a non-empty string, encode the string such that its encoded length is the shortest.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.
Note:
  1. k will be a positive integer and encoded string will not be empty or have extra space.
  2. You may assume that the input string contains only lowercase English letters. The string's length is at most 160.
  3. If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them is fine.
Example 1:
Input: "aaa"
Output: "aaa"
Explanation: There is no way to encode it such that it is shorter than the input string, so we do not encode it.
Example 2:
Input: "aaaaa"
Output: "5[a]"
Explanation: "5[a]" is shorter than "aaaaa" by 1 character.
Example 3:
Input: "aaaaaaaaaa"
Output: "10[a]"
Explanation: "a9[a]" or "9[a]a" are also valid solutions, both of them have the same length = 5, which is the same as "10[a]".
Example 4:
Input: "aabcaabcd"
Output: "2[aabc]d"
Explanation: "aabc" occurs twice, so one answer can be "2[aabc]d".
Example 5:
Input: "abbbabbbcabbbabbbc"
Output: "2[2[abbb]c]"
Explanation: "abbbabbbc" occurs twice, but "abbbabbbc" can also be encoded to "2[abbb]c", so one answer can be "2[2[abbb]c]".
https://chenboxie.wordpress.com/2018/07/08/leetcode-471-encode-string-with-shortest-length/
区间DP的问题,我们用dp[i][j]表示子串s[i:j]的最小压缩串,我们有如下递推方程:
  • dp[i][j] = min(dp[i][k] + dp[k + 1][j]), where 1 <= k < j, ‘+’ means concatenate here
  • dp[i][j] = min(dp[i][j], compress(s[i:j])), compress is a function to find if we can shorten input string by find a repeating pattern in itself
这里两个递推公式,第一个递推适用于 abcabcd这种string,在k = 5的时候, dp(abcabcd) = dp(abcabc) + dp(d) = 2[abc] + d = 2[abc]d
2. 但仅仅使用第一个递推是不够的,例如这个例子,abcabcabc, 用第一个递推公式可以得到, dp(abcabcabc) = dp(abcabc) + dp(abc) = 2[abc] + abc = 2[abc]abc,永远无法得到3[abc]
所以由此我们需要第二个递推:
这里compress的功能是,找到string自身的重复串来压缩string。比如对于abcabcabc,我们只进行区间dp是没有办法找到3[abc]的,所以我们必须对自身进行compress。
这里就引出很重要的一个技巧:
我们在字符串t后面再加上一个t,然后在这里面寻找子字符串t的第二个起始位置,如果第二个起始位置小于t的长度的话,说明t包含重复字符串,举个例子吧,比如 t = “abab”, 那么t+t = “abababab”,我们在里面找第二个t出现的位置为2,小于t的长度4,说明t中有重复出现,重复的个数为t.size()/pos = 2个
3. 假设自身的字符串为sub, 在对自身进行压缩的过程中,如果自身是符合压缩条件的,压缩必须写成:
sub = sub.length() / index + “[” + dp[i][i + index – 1] + “]”;
举个例子,比如
sub = “abcdbcd abcdbcd”,不能写成2[abcdbcd], 而是写成2[a2[bcd]]
总结:
1. 区间DP的辨别和运用,dp[i][j] = max/min(dp[i][k] + dp[k + 1][j])
2. 像s=abcabc这样的字符串,在O(n)时间内进行压缩的方法,就是在s + s中寻找s的第二个起始位置,如果第二个起始位置小于s的长度的话,说明s包含重复字符串。
这道题还是应该用动态规划来做。我们建立一个二维的DP数组,其中dp[i][j]表示s在[i, j]范围内的字符串的缩写形式(如果缩写形式长度大于子字符串,那么还是保留子字符串),那么如果s字符串的长度是n,最终我们需要的结果就保存在dp[0][n-1]中,然后我们需要遍历s的所有子字符串,对于任意一段子字符串[i, j],我们我们以中间任意位置k来拆分成两段,比较dp[i][k]加上dp[k+1][j]的总长度和dp[i][j]的长度,将长度较小的字符串赋给dp[i][j],然后我们要做的就是在s中取出[i, j]范围内的子字符串t进行合并。合并的方法是我们在取出的字符串t后面再加上一个t,然后在这里面寻找子字符串t的第二个起始位置,如果第二个起始位置小于t的长度的话,说明t包含重复字符串,举个例子吧,比如 t = "abab", 那么t+t = "abababab",我们在里面找第二个t出现的位置为2,小于t的长度4,说明t中有重复出现,重复的个数为t.size()/pos = 2个,那么我们就要把重复的地方放入中括号中,注意中括号里不能直接放这个子字符串,而是应该从dp中取出对应位置的字符串,因为重复的部分有可能已经写成缩写形式了,比如题目中的例子5。如果t = "abc",那么t+t = "abcabc",我们在里面找第二个t出现的位置为3,等于t的长度3,说明t中没有重复出现,那么replace就还是t。然后我们比较我们得到的replace和dp[i][j]中的字符串长度,把长度较小的赋给dp[i][j]即可,时间复杂度为O(n3),空间复杂度为O(n2)。

这里compress的功能是,找到string自身的重复串来压缩string。比如对于abcabcabc,我们只进行区间dp是没有办法找到3[abc]的,所以我们必须对自身进行compress。对自身进行压缩的就是寻找自身最小覆盖子串的过程。有多个覆盖子串我们肯定是取最小的,对于d[str]的形式,如果我们double str的长度最多也就使得d减少一位,所以str越短越好。
时间复杂度O(n^3),寻找自身最小覆盖子串需要线性时间,代码如下:

https://discuss.leetcode.com/topic/71963/accepted-solution-in-java
We will form 2-D array of Strings.
dp[i][j] = string from index i to index j in encoded form.
We can write the following formula as:-
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) or if we can find some pattern in string from i to j which will result in more less length.
Time Complexity = O(n^3)
Time Complexity is O(N^4), replaceAll() is O(N)
    String[][] dp = new String[s.length()][s.length()];
    
    for(int l=0;l<s.length();l++) {
        for(int i=0;i<s.length()-l;i++) {
            int j = i+l;
            String substr = s.substring(i, j+1);
            // Checking if string length < 5. In that case, we know that encoding will not help.
            if(j - i < 4) {
                dp[i][j] = substr;
            } else {
                dp[i][j] = substr;
                // Loop for trying all results that we get after dividing the strings into 2 and combine the   results of 2 substrings
                for(int k = i; k<j;k++) {
                    if((dp[i][k] + dp[k+1][j]).length() < dp[i][j].length()){
                        dp[i][j] = dp[i][k] + dp[k+1][j];
                    }
                }
                
                // Loop for checking if string can itself found some pattern in it which could be repeated.
                for(int k=0;k<substr.length();k++) {
                    String repeatStr = substr.substring(0, k+1);
                    if(repeatStr != null 
                       && substr.length()%repeatStr.length() == 0 
                       && substr.replaceAll(repeatStr, "").length() == 0) {
                          String ss = substr.length()/repeatStr.length() + "[" + dp[i][i+k] + "]";
                          if(ss.length() < dp[i][j].length()) {
                            dp[i][j] = ss;
                          }
                     }
                }
            }
        }
    }
    
    return dp[0][s.length()-1];
}

X.
http://www.cnblogs.com/grandyang/p/6194403.html
我们建立一个二维的DP数组,其中dp[i][j]表示s在[i, j]范围内的字符串的缩写形式(如果缩写形式长度大于子字符串,那么还是保留子字符串),那么如果s字符串的长度是n,最终我们需要的结果就保存在dp[0][n-1]中,然后我们需要遍历s的所有子字符串,对于任意一段子字符串[i, j],我们我们以中间任意位置k来拆分成两段,比较dp[i][k]加上dp[k+1][j]的总长度和dp[i][j]的长度,将长度较小的字符串赋给dp[i][j],

然后我们要做的就是在s中取出[i, j]范围内的子字符串t进行合并。合并的方法是我们在取出的字符串t后面再加上一个t,然后在这里面寻找子字符串t的第二个起始位置,如果第二个起始位置小于t的长度的话,说明t包含重复字符串,举个例子吧,比如 t = "abab", 那么t+t = "abababab",我们在里面找第二个t出现的位置为2,小于t的长度4,说明t中有重复出现,重复的个数为t.size()/pos = 2个,那么我们就要把重复的地方放入中括号中,注意中括号里不能直接放这个子字符串,而是应该从dp中取出对应位置的字符串,因为重复的部分有可能已经写成缩写形式了,比如题目中的例子5。如果t = "abc",那么t+t = "abcabc",我们在里面找第二个t出现的位置为3,等于t的长度3,说明t中没有重复出现,那么replace就还是t。然后我们比较我们得到的replace和dp[i][j]中的字符串长度,把长度较小的赋给dp[i][j]即可,时间复杂度为O(n3),空间复杂度为O(n2),

    string encode(string s) {
        int n = s.size();
        vector<vector<string>> dp(n, vector<string>(n, ""));
        for (int step = 1; step <= n; ++step) {
            for (int i = 0; i + step - 1 < n; ++i) {
                int j = i + step - 1;
                dp[i][j] = s.substr(i, step);
                for (int k = i; k < j; ++k) {
                    string left = dp[i][k], right = dp[k + 1][j];
                    if (left.size() + right.size() < dp[i][j].size()) {
                        dp[i][j] = left + right;
                    }
                }
                string t = s.substr(i, j - i + 1), replace = "";
                auto pos = (t + t).find(t, 1);
                if (pos >= t.size()) replace = t;
                else replace = to_string(t.size() / pos) + '[' + dp[i][i + pos - 1] + ']';
                if (replace.size() < dp[i][j].size()) dp[i][j] = replace;
            }
        }
        return dp[0][n - 1];
    }

我们可以优化上面的方法。如果t是重复的,是不是就不需要再看left.size() + right.size() < dp[i][j].size()了。例如t是abcabcabcabcabc, 最终肯定是5[abc],不需要再看3[abc]+abcabc或者abcabc+3[abc]。对于一个本身就重复的字符串,最小的长度肯定是n[REPEATED],不会是某个left+right。所以应该把k的那个循环放在t和replace那部分代码的后面。这样的确提高了一些运算效率的

    string encode(string s) {
        int n = s.size();
        vector<vector<string>> dp(n, vector<string>(n, ""));
        for (int step = 1; step <= n; ++step) {
            for (int i = 0; i + step - 1 < n; ++i) {
                int j = i + step - 1;
                dp[i][j] = s.substr(i, step);
                string t = s.substr(i, j - i + 1), replace = "";
                auto pos = (t + t).find(t, 1);
                if (pos < t.size()) {
                    replace = to_string(t.size() / pos) + "[" + dp[i][i + pos - 1] + "]";
                    if (replace.size() < dp[i][j].size()) dp[i][j] = replace;
                    continue;
                }
                for (int k = i; k < j; ++k) {
                    string left = dp[i][k], right = dp[k + 1][j];
                    if (left.size() + right.size() < dp[i][j].size()) {
                        dp[i][j] = left + right;
                    }
                }
            }
        }
        return dp[0][n - 1];
    }

https://segmentfault.com/a/1190000008341304
dpi表示s[i, j]最短的压缩结果,subproblem里面枚举切分点k,分别得到dpi和dpk+1求和,找到长度最短的。
这道题关键是找sub = abcabc这种可压缩的情况,其中sub = s[i,j]。方法比较巧妙,用sub+sub = abcabcabcabc,找第二个s在s+s里出现的位置,如果不是len(sub),则说明sub有重复,那么就要压缩这个sub,重复次数是len(sub) / indexOf(sub, 1),重复的string用的是之前压缩过的dpi,index = indexOf(sub, 1)。
    public String encode(String s) {
        int n = s.length();
        String[][] dp = new String[n][n];
        for(int i = 0; i < n; i++) dp[i][i] = "" + s.charAt(i);
        // j - i
        for(int len = 1; len < n; len++) {
            for(int i = 0; i + len < n; i++) {
                int j = i + len;
                // enumerate seperate k
                for(int k = i; k < j; k++) {
                    int left = dp[i][k].length();
                    int right = dp[k+1][j].length();
                    // update shortest encoded string within (i, j)
                    if(dp[i][j] == null || left + right < dp[i][j].length()) {
                        dp[i][j] = dp[i][k] + dp[k+1][j];
                    }
                }
                // update string within (i, j), encode abcabc
                String sub = s.substring(i, j + 1);
                int index = (sub + sub).indexOf(sub, 1);
                if(index < sub.length()) {
                    sub = (sub.length() / index) + "[" + dp[i][i+index-1] + "]";
                }
                if(dp[i][j] == null || dp[i][j].length() > sub.length()) {
                    dp[i][j] = sub;
                }
            }
        }
        
        return dp[0][n-1];
    }
http://www.cnblogs.com/EdwardLiu/p/6213476.html
Initially I think of 1D DP, dp[i] stands for the shortest string of first i characters, then:
dp[i] = minLen{dp[k] + encode(substring(k+1, i))}
then I realize that the second part encode(substring(k+1, i)) is actually the same with our dp problem. So it turns out the transfer function is
dp[i] = minLen{dp[k] + dp(substring(k+1, i))}
then 1D is not enough, I introduce the second dimension, which indicates the end. dp[i][j] is the shortest encoded string from i to j
But the hardest part of this problem is how to generate dp[i][j] from dp[i][k] and dp[k+1][j]
I‘ve thought about the cases like: 
dp[i][k] = 3[abc]   dp[k+1][j] = 2[abc],   then dp[i][j] = 5[abc]
dp[i][k] = 3[abc]   dp[k+1][j] = xyz,   then dp[i][j] = 3[abc]xyz
dp[i][k] = aabc   dp[k+1][j] = aabc,   then dp[i][j] = 2[aabc]
No idea what to implement this conveniently, so refer to idea  
The idea is to firstly concantenate dp[i][k] and dp[k+1][j] directly to construct dp[i][j], and then check if there exist possible repeat patterns in the original substring s.substring(i, j+1) that could further shorten dp[i][j]


replaceAll function is really clever
https://hbisheng.gitbooks.io/leetcode-google/content/471-encode-string-with-shortest-length.html
记忆化搜索
利用字典dp记录字符串的最优编码串

枚举分隔点p, 将字符串拆解为left, right左右两部分

尝试将left调用solve函数进行编码压缩,并对right递归调用encode函数进行搜索

将left和right组合的最短字符串返回,并更新dp
def __init__(self): self.dp = dict() def encode(self, s): """ :type s: str :rtype: str """ size = len(s) if size <= 1: return s if s in self.dp: return self.dp[s] ans = s for p in range(1, size + 1): left, right = s[:p], s[p:] t = self.solve(left) + self.encode(right) if len(t) < len(ans): ans = t self.dp[s] = ans return ans def solve(self, s): ans = s size = len(s) for x in range(1, size / 2 + 1): if size % x or s[:x] * (size / x) != s: continue y = str(size / x) + '[' + self.encode(s[:x]) + ']' if len(y) < len(ans): ans = y return ans


https://yijiajin.github.io/leetcode/2017/01/02/LC471.-Encode-String-with-Shortest-Length/
利用KMP算法来寻找和判断是否存在重复的子串是比较快的。顺便这是LC459题。
public String encode(String s) { // dp solution, for each substring of s, check whether it can be encode // dp[i][j] means substing of [i, j] after encode if(s == null || s.length() <= 4) return s; int len = s.length(); String[][] dp = new String[len][len]; for(int sublen = 0; sublen < len; sublen++){ for(int begin = 0; begin < len - sublen; begin++){ int end = begin + sublen; String sub = s.substring(begin, end + 1); dp[begin][end] = sub; if(sublen < 4) continue; // sub.length = sublen + 1 // get shortest substring combination for(int i = begin; i < end; i++){ if(dp[begin][i].length() + dp[i+1][end].length() < dp[begin][end].length()) dp[begin][end] = dp[begin][i] + dp[i+1][end]; } // if repeat, using kmp to encode then compare with shortest combination String pattern = kmp(sub); //System.out.println(pattern); // no repeat, keep origional -> shorest combination  if(pattern.length() == sub.length()) continue; // find repeat, repeat should also be encoded String encode = sub.length()/pattern.length() + "[" + dp[begin][begin+pattern.length()-1] + "]"; if(encode.length() < dp[begin][end].length()) dp[begin][end] = encode; } // for begin  } // for sublen return dp[0][len - 1]; } // code // kmp method to find repeat pattern in one String private String kmp(String str){ int len = str.length(); int[] next = new int[len]; char[] arr = str.toCharArray(); Arrays.fill(next, -1); int i = 0, j = 1; for(; j < len; j++){ i = next[j - 1]; while(arr[i + 1] != arr[j] && i >= 0) i = next[i]; if(arr[i + 1] == arr[j]) next[j] = i + 1; else next[j] = -1; } //System.out.println(Arrays.toString(next)); // if repeat, it must before the 0 int patternLen = len - next[len - 1] - 1; if(patternLen == 0) return str; if(patternLen != len && len % patternLen == 0) { return str.substring(0, patternLen); } else { return str; } } // kmp

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1070) Review (884) Algorithm (668) to-do (610) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (185) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (77) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Company - Google (63) Interval (63) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Codility (53) Priority Queue (53) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Backtracking (40) Data Structure Design (40) Graph (40) Data Structure (39) Jobdu (39) LeetCode - DP (39) Random (39) Codeforces (38) Knapsack (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (32) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Company-Zenefits (28) Code - Detail (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) Reverse Thinking (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) Left and Right Array (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Long Increasing Sequence(LIS) (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Scan from right (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts