diff --git a/framework-t/src/android/net/nsd/NsdManager.java b/framework-t/src/android/net/nsd/NsdManager.java
index 27b4955..f6e1324 100644
--- a/framework-t/src/android/net/nsd/NsdManager.java
+++ b/framework-t/src/android/net/nsd/NsdManager.java
@@ -57,7 +57,6 @@
 import java.lang.annotation.Retention;
 import java.lang.annotation.RetentionPolicy;
 import java.util.ArrayList;
-import java.util.List;
 import java.util.Objects;
 import java.util.concurrent.Executor;
 import java.util.regex.Matcher;
@@ -167,7 +166,28 @@
      * A regex for the acceptable format of a type or subtype label.
      * @hide
      */
-    public static final String TYPE_SUBTYPE_LABEL_REGEX = "_[a-zA-Z0-9-_]{1,61}[a-zA-Z0-9]";
+    public static final String TYPE_LABEL_REGEX = "_[a-zA-Z0-9-_]{1,61}[a-zA-Z0-9]";
+
+    /**
+     * A regex for the acceptable format of a subtype label.
+     *
+     * As per RFC 6763 7.1, "Subtype strings are not required to begin with an underscore, though
+     * they often do.", and "Subtype strings [...] may be constructed using arbitrary 8-bit data
+     * values.  In many cases these data values may be UTF-8 [RFC3629] representations of text, or
+     * even (as in the example above) plain ASCII [RFC20], but they do not have to be.".
+     *
+     * This regex is overly conservative as it mandates the underscore and only allows printable
+     * ASCII characters (codes 0x20 to 0x7e, space to tilde), except for comma (0x2c) and dot
+     * (0x2e); so the NsdManager API does not allow everything the RFC allows. This may be revisited
+     * in the future, but using arbitrary bytes makes logging and testing harder, and using other
+     * characters would probably be a bad idea for interoperability for apps.
+     * @hide
+     */
+    public static final String SUBTYPE_LABEL_REGEX = "_["
+            + "\\x20-\\x2b"
+            + "\\x2d"
+            + "\\x2f-\\x7e"
+            + "]{1,62}";
 
     /**
      * A regex for the acceptable format of a service type specification.
@@ -180,14 +200,14 @@
     public static final String TYPE_REGEX =
             // Optional leading subtype (_subtype._type._tcp)
             // (?: xxx) is a non-capturing parenthesis, don't capture the dot
-            "^(?:(" + TYPE_SUBTYPE_LABEL_REGEX + ")\\.)?"
+            "^(?:(" + SUBTYPE_LABEL_REGEX + ")\\.)?"
                     // Actual type (_type._tcp.local)
-                    + "(" + TYPE_SUBTYPE_LABEL_REGEX + "\\._(?:tcp|udp))"
+                    + "(" + TYPE_LABEL_REGEX + "\\._(?:tcp|udp))"
                     // Drop '.' at the end of service type that is compatible with old backend.
                     // e.g. allow "_type._tcp.local."
                     + "\\.?"
                     // Optional subtype after comma, for "_type._tcp,_subtype1,_subtype2" format
-                    + "((?:," + TYPE_SUBTYPE_LABEL_REGEX + ")*)"
+                    + "((?:," + SUBTYPE_LABEL_REGEX + ")*)"
                     + "$";
 
     /**
diff --git a/service-t/src/com/android/server/NsdService.java b/service-t/src/com/android/server/NsdService.java
index 34927a6..edd4818 100644
--- a/service-t/src/com/android/server/NsdService.java
+++ b/service-t/src/com/android/server/NsdService.java
@@ -26,8 +26,8 @@
 import static android.net.nsd.NsdManager.MDNS_DISCOVERY_MANAGER_EVENT;
 import static android.net.nsd.NsdManager.MDNS_SERVICE_EVENT;
 import static android.net.nsd.NsdManager.RESOLVE_SERVICE_SUCCEEDED;
+import static android.net.nsd.NsdManager.SUBTYPE_LABEL_REGEX;
 import static android.net.nsd.NsdManager.TYPE_REGEX;
-import static android.net.nsd.NsdManager.TYPE_SUBTYPE_LABEL_REGEX;
 import static android.provider.DeviceConfig.NAMESPACE_TETHERING;
 
 import static com.android.modules.utils.build.SdkLevel.isAtLeastU;
@@ -1760,7 +1760,7 @@
 
     /** Returns {@code true} if {@code subtype} is a valid DNS-SD subtype label. */
     private static boolean checkSubtypeLabel(String subtype) {
-        return Pattern.compile("^" + TYPE_SUBTYPE_LABEL_REGEX + "$").matcher(subtype).matches();
+        return Pattern.compile("^" + SUBTYPE_LABEL_REGEX + "$").matcher(subtype).matches();
     }
 
     @VisibleForTesting
diff --git a/tests/cts/net/src/android/net/cts/NsdManagerTest.kt b/tests/cts/net/src/android/net/cts/NsdManagerTest.kt
index 9aa3c84..43aa8a6 100644
--- a/tests/cts/net/src/android/net/cts/NsdManagerTest.kt
+++ b/tests/cts/net/src/android/net/cts/NsdManagerTest.kt
@@ -114,7 +114,6 @@
 import kotlin.math.min
 import kotlin.test.assertEquals
 import kotlin.test.assertFailsWith
-import kotlin.test.assertNotEquals
 import kotlin.test.assertNotNull
 import kotlin.test.assertNull
 import kotlin.test.fail
@@ -127,7 +126,6 @@
 import org.junit.Rule
 import org.junit.Test
 import org.junit.runner.RunWith
-import kotlin.test.assertNotEquals
 
 private const val TAG = "NsdManagerTest"
 private const val TIMEOUT_MS = 2000L
@@ -1108,6 +1106,51 @@
     }
 
     @Test
+    fun testSubtypeAdvertisingAndDiscovery_nonAlphanumericalSubtypes() {
+        // All non-alphanumerical characters between 0x20 and 0x7e, with a leading underscore
+        val nonAlphanumSubtype = "_ !\"#\$%&'()*+-/:;<=>?@[\\]^_`{|}"
+        // Test both legacy syntax and the subtypes setter, on different networks
+        val si1 = makeTestServiceInfo(network = testNetwork1.network).apply {
+            serviceType = "$serviceType,_test1,$nonAlphanumSubtype"
+        }
+        val si2 = makeTestServiceInfo(network = testNetwork2.network).apply {
+            subtypes = setOf("_test2", nonAlphanumSubtype)
+        }
+
+        val registrationRecord1 = NsdRegistrationRecord()
+        val registrationRecord2 = NsdRegistrationRecord()
+        val subtypeDiscoveryRecord1 = NsdDiscoveryRecord()
+        val subtypeDiscoveryRecord2 = NsdDiscoveryRecord()
+        tryTest {
+            registerService(registrationRecord1, si1)
+            registerService(registrationRecord2, si2)
+            nsdManager.discoverServices(DiscoveryRequest.Builder(serviceType)
+                .setSubtype(nonAlphanumSubtype)
+                .setNetwork(testNetwork1.network)
+                .build(), { it.run() }, subtypeDiscoveryRecord1)
+            nsdManager.discoverServices("$nonAlphanumSubtype.$serviceType",
+                NsdManager.PROTOCOL_DNS_SD, testNetwork2.network, { it.run() },
+                subtypeDiscoveryRecord2)
+
+            val discoveredInfo1 = subtypeDiscoveryRecord1.waitForServiceDiscovered(serviceName,
+                serviceType, testNetwork1.network)
+            val discoveredInfo2 = subtypeDiscoveryRecord2.waitForServiceDiscovered(serviceName,
+                serviceType, testNetwork2.network)
+            assertTrue(discoveredInfo1.subtypes.contains(nonAlphanumSubtype))
+            assertTrue(discoveredInfo2.subtypes.contains(nonAlphanumSubtype))
+        } cleanupStep {
+            nsdManager.stopServiceDiscovery(subtypeDiscoveryRecord1)
+            subtypeDiscoveryRecord1.expectCallback<DiscoveryStopped>()
+        } cleanupStep {
+            nsdManager.stopServiceDiscovery(subtypeDiscoveryRecord2)
+            subtypeDiscoveryRecord2.expectCallback<DiscoveryStopped>()
+        } cleanup {
+            nsdManager.unregisterService(registrationRecord1)
+            nsdManager.unregisterService(registrationRecord2)
+        }
+    }
+
+    @Test
     fun testSubtypeDiscovery_typeMatchButSubtypeNotMatch_notDiscovered() {
         val si1 = makeTestServiceInfo(network = testNetwork1.network).apply {
             serviceType += ",_subtype1"